Submission #57063329

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i(l),i##End(r); i<=i##End; ++i)
#define rep_(i,l,r) for(int i(l),i##End(r); i<i##End; ++i)
#define per(i,l,r) for(int i(r),i##End(l); i>=i##End; --i)
#define per_(i,l,r) for(int i(r),i##End(l); i>i##End; --i)
#define kid(i,x,G) for(int i=G.ls[x];i;i=G.nx[i])
#define endl '\n'
using namespace std;
using ll=long long;
using ull=long long unsigned;
using uint=unsigned int;
using db=double;
using ldb=long double;
using i128=__int128;
using ui128=unsigned __int128;
using bo=bool;
template<typename T> constexpr T inf = 0;
template<> constexpr int inf<int> = 1e9;
template<> constexpr ll inf<ll> = 1e18;
template<> constexpr db inf<db> = 1e18;
template<> constexpr ldb inf<ldb> = 1e18;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i(l),i##End(r); i<=i##End; ++i)
#define rep_(i,l,r) for(int i(l),i##End(r); i<i##End; ++i)
#define per(i,l,r) for(int i(r),i##End(l); i>=i##End; --i)
#define per_(i,l,r) for(int i(r),i##End(l); i>i##End; --i)
#define kid(i,x,G) for(int i=G.ls[x];i;i=G.nx[i])
#define endl '\n'
using namespace std;
using ll=long long;
using ull=long long unsigned;
using uint=unsigned int;
using db=double;
using ldb=long double;
using i128=__int128;
using ui128=unsigned __int128;
using bo=bool;
template<typename T> constexpr T inf = 0;
template<> constexpr int inf<int> = 1e9;
template<> constexpr ll inf<ll> = 1e18;
template<> constexpr db inf<db> = 1e18;
template<> constexpr ldb inf<ldb> = 1e18;
constexpr db eps=1e-12;
#define vec vector
template<typename T> using heap=priority_queue<T,vec<T>,greater<T>>;
template<typename T> using big_heap=priority_queue<T>;
#define clock() chrono::steady_clock::now()
const auto start_time=clock();
template<typename T=db> T runtime() {return chrono::duration<T>(clock()-start_time).count();}
mt19937 rnd(random_device{}());
void Yes(bo f=true) {cout<<(f?"Yes":"No")<<endl;}
void No(bo f=true) {Yes(!f);}
void yes(bo f=true) {cout<<(f?"yes":"no")<<endl;}
void no(bo f=true) {yes(!f);}
void YES(bo f=true) {cout<<(f?"YES":"NO")<<endl;}
void NO(bo f=true) {YES(!f);}
ll qpow(ll a,ll n,ll p)
{
	ll x=1;
	for(;n;n>>=1,a=(i128)a*a%p)
		if(n&1) x=(i128)x*a%p;
	return x;
}
constexpr int
	N=1e5+5,
	M=0,
	K=0,
	Q=0,
	S=0,
	B=50,
	P=998244353 //1e9+7
;
struct Graph
{
	int e[M],ls[N],nx[M],em;
	void lian(int x,int y) {e[++em]=y,nx[em]=ls[x],ls[x]=em;}
};
struct v_Graph
{
	int e[M][2],ls[N],nx[M],em;
	void lian(int x,int y,int z) {e[++em][0]=y,e[em][1]=z,nx[em]=ls[x],ls[x]=em;}
};
// #define MULTITEST
// #define FILE_IO_NAME ""

#define X 1,n,1
#define Y int x,int y,int p
#define D int mid=(x+y)/2
#define ls x,mid,p*2
#define rs mid+1,y,p*2+1
ll t[N*5];
ll fnd(Y,int l,int r)
{
	if(x>r||y<l) return 0;
	if(l<=x&&y<=r) return t[p];
	D;return fnd(ls,l,r)+fnd(rs,l,r);
}
void cng(Y,int w,int v)
{
	if(x==y) {t[p]=v;return;}
	D;
	if(mid>=w) cng(ls,w,v);
	else cng(rs,w,v);
	t[p]=t[p*2]+t[p*2+1];
}

int n,q,ty,u,v,ku,kv,l[N],r[N],g,p;
ll a[N],b[N],z;
set<int> s;
set<int>::iterator si;
void _main()
{
	cin>>n;
	rep(i,1,n) cin>>a[i],cng(X,i,a[i]);
	rep(i,1,n)
	{
		cin>>b[i];
		if(b[i]!=1) s.insert(i);
	}
	cin>>q;
	while(q--)
	{
		cin>>ty>>u>>v;
		if(ty==1) a[u]=v,cng(X,u,v);
		if(ty==2)
		{
			if(b[u]!=1) s.erase(u);
			b[u]=v;
			if(b[u]!=1) s.insert(u);
		}
		if(ty==3)
		{
			p=u,z=0;
			while(1)
			{
				si=s.lower_bound(p);
				if(si==s.end()||(*si)>v)
					{z+=fnd(X,p,v);break;}
				z+=fnd(X,p,(*si)-1),p=(*si);
				z=max(z+a[p],z*b[p]),p++;
			}
			cout<<z<<endl;
		}
	}
}

int main() {
#if defined(FILE_IO_NAME) && !defined(ONLINE_JUDGE)
	freopen(FILE_IO_NAME".in","r",stdin);
	freopen(FILE_IO_NAME".out","w",stdout);
#endif
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cout<<fixed<<setprecision(15);
	int T=1;
#if defined(MULTITEST)
	cin>>T;
#endif
	while(T--) _main();
	return 0;
}

Submission Info

Judge Result