QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#721775#8338. Quad Kingdoms ChessAnotherDayofSun#WA 14ms20088kbC++142.4kb2024-11-07 16:48:112024-11-07 16:48:11

Judging History

This is the latest submission verdict.

  • [2024-11-07 16:48:11]
  • Judged
  • Verdict: WA
  • Time: 14ms
  • Memory: 20088kb
  • [2024-11-07 16:48:11]
  • Submitted

answer

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++) 
#define re
#define vi vector<int>
#define pb push_back
#define ll long long
#define P 998244353
using namespace std;
inline int read(){
	re char c;int res=0;bool flag=0;
	while(c=getchar(),c<48)(c=='-')&&(flag=1);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
	flag&&(res=-res);
	return res; 
}
const int MN=1e5+5; 
int n,a[MN]; 
struct ds {
	static const int N=MN<<2; 
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define mid ((l+r)>>1)
	int mx[N],cnt[N];
	ll sum[N],ans[N]; 
	void qry2(int k,int l,int r,int &tcnt,ll &tsum,ll &tans,int nowmx) {
		if(l==r) {
			if(mx[k]>=nowmx) tcnt=cnt[k],tsum=sum[k],tans=ans[k];
			else tcnt=0,tsum=0,tans=0;
			return; 
		}
		if(mx[rs]>=nowmx) {
			qry2(rs,mid+1,r,tcnt,tsum,tans,nowmx); 
			int lcnt=cnt[k]-cnt[rs]; 
			int lsum=sum[k]-sum[rs];
			int lans=(ans[k]-ans[rs])-lsum*cnt[rs];
			tcnt+=lcnt,tsum+=lsum,tans+=lans;
		} else qry2(ls,l,mid,tcnt,tsum,tans,nowmx); 
	}
	void pushup(int k,int l,int r) {
		mx[k]=max(mx[ls],mx[rs]);
		if(mx[rs]>mx[ls]) cnt[k]=cnt[rs],sum[k]=sum[rs],ans[k]=ans[rs]; 
		else {
			int tcnt; ll tsum,tans; 
			qry2(ls,l,mid,tcnt,tsum,tans,mx[rs]);
			cnt[k]=tcnt+cnt[rs],sum[k]=tsum+sum[rs],ans[k]=tans+tsum*cnt[rs]+ans[rs];
		}
	}
	void upd(int k,int l,int r,int p,int v) {
		if(l==r) {
			mx[k]=sum[k]=ans[k]=v; 
			cnt[k]=1; 
			return; 
		}
		if(p<=mid) upd(ls,l,mid,p,v); 
		else upd(rs,mid+1,r,p,v); 
		pushup(k,l,r); 
	}
	void build(int k,int l,int r,int *a) {
		if(l==r) {
			mx[k]=sum[k]=ans[k]=a[l]; 
			cnt[k]=1; 
			return; 
		}
		build(ls,l,mid,a),build(rs,mid+1,r,a); 
		pushup(k,l,r); 
	}
	pair<ll,int> qry() {
		return make_pair(ans[1],cnt[1]); 
	}
	#undef mid
}; 
struct tpw {
	static const int N=4e5+5; 
	int n,a[N];  ds t;
	void rd() {
		n=read();
		For(i,1,n) a[i]=read();
		t.build(1,1,n,a); 
		
	}
	void mdf(int x,int y) {
		a[x]=y; 
		t.upd(1,1,n,x,y); 
	}
	pair<ll,int> qry() {
		return t.qry(); 
	}
} line[2]; 
void works() {
	line[0].rd();
	line[1].rd();
	int m=read();
	while(m--) {
		int o=read(),x=read(),y=read();
		line[o-1].mdf(x,y); 
		// cerr<<line[0].qry().first<<' '<<line[1].qry().first<<endl;
		if(line[0].qry()==line[1].qry()) printf("YES\n"); 
		else printf("NO\n"); 
	} 

}
	
signed main() {
	int T=1;
	while(T--) {
		works(); 
	}

	return 0; 
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 18020kb

input:

5
1 2 3 4 5
5
5 4 3 2 1
8
1 1 5
1 4 2
1 2 4
1 5 1
1 5 5
2 1 4
2 3 5
2 5 5

output:

NO
NO
NO
YES
NO
NO
NO
YES

result:

ok 8 tokens

Test #2:

score: 0
Accepted
time: 11ms
memory: 20068kb

input:

1
2
6
2 1 1 1 1 1
200000
2 6 2
1 1 1
1 1 1
1 1 2
2 1 1
1 1 2
1 1 1
2 4 1
2 1 2
1 1 1
1 1 2
2 5 1
1 1 1
1 1 2
1 1 1
2 6 1
1 1 2
1 1 2
1 1 2
2 3 1
1 1 1
2 1 1
2 6 2
1 1 2
2 4 1
1 1 2
2 6 1
1 1 2
1 1 1
2 5 2
2 6 2
1 1 1
2 4 2
2 5 2
2 6 2
1 1 1
2 5 1
2 6 2
1 1 2
1 1 1
1 1 1
2 4 1
1 1 2
1 1 2
1 1 2
2 3 2...

output:

NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #3:

score: 0
Accepted
time: 10ms
memory: 18032kb

input:

6
2 1 1 2 1 2
1
1
200000
2 1 1
1 1 2
1 1 1
2 1 2
2 1 1
2 1 1
2 1 2
2 1 2
1 1 2
1 3 1
1 6 2
1 5 2
1 4 2
1 3 1
2 1 2
1 4 2
1 4 2
2 1 2
2 1 2
1 3 1
1 6 1
1 1 2
2 1 1
1 6 1
1 3 1
1 5 2
1 6 2
1 5 2
2 1 2
1 2 1
1 5 2
2 1 1
2 1 1
1 6 1
2 1 2
2 1 1
1 3 2
2 1 1
1 6 1
1 4 2
1 2 1
1 1 1
2 1 1
1 2 1
1 6 2
1 6 2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 tokens

Test #4:

score: -100
Wrong Answer
time: 14ms
memory: 20088kb

input:

6
1 3 1 2 1 2
6
2 1 3 3 3 1
200000
2 4 2
1 2 1
1 6 2
2 3 2
1 1 1
1 6 2
1 6 2
1 3 2
2 6 1
2 4 3
1 1 2
2 5 2
2 6 2
2 3 1
1 4 3
1 3 1
2 5 2
2 4 2
2 1 3
1 1 1
2 2 2
2 4 2
1 5 3
1 6 3
2 6 3
1 5 3
2 5 3
2 4 1
2 4 2
1 1 2
1 6 1
2 6 1
1 2 3
1 1 3
1 1 1
2 6 3
2 4 1
1 4 2
2 2 1
1 3 1
1 1 3
1 1 3
1 4 3
1 3 3
2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer 27th words differ - expected: 'YES', found: 'NO'