QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394007#8338. Quad Kingdoms Chessucup-team3282WA 55ms18428kbC++142.1kb2024-04-19 20:31:432024-04-19 20:31:44

Judging History

你现在查看的是最新测评结果

  • [2024-04-19 20:31:44]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:18428kb
  • [2024-04-19 20:31:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+9;
const int base=100003;
int pb[maxn];

int m;

struct seg_tree{
	#define ls(u) ((u)<<1)
	#define rs(u) ((u)<<1|1)
		
	int n;
	int a[maxn];
	int L[maxn<<2],R[maxn<<2];
	int mx[maxn<<2],cnt[maxn<<2],h[maxn<<2];//cnt[u] ½ö¿¼ÂÇ L[u]-R[u] ºó ls(u) µÄ´ð°¸ 
	
	pair<int,int> cal(int u,int x){
		if(L[u]==R[u]){
			if(mx[u]>x)
				return {1,h[u]};
			else
				return {0,0};
		}
		if(mx[rs(u)]>x){
			pair<int,int> t=cal(rs(u),x);
			return {cnt[u]+t.first,(t.second+(ll)h[u]*pb[t.first])%mod};
		}
		return cal(ls(u),x);
	}
	
	void push_up(int u){
		mx[u]=max(mx[ls(u)],mx[rs(u)]);
		pair<int,int> t=cal(ls(u),mx[rs(u)]);
		cnt[u]=t.first;
		h[u]=t.second;
	}
	void build(int u,int l,int r){
		L[u]=l;R[u]=r;
		if(l==r){
			mx[u]=a[l];
			cnt[u]=1;
			h[u]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(ls(u),l,mid);
		build(rs(u),mid+1,r);
		push_up(u);
//		cout<<"build "<<u<<' '<<l<<' '<<r<<' '<<mx[u]<<' '<<cnt[u]<<' '<<h[u]<<endl;
	}
	void modify(int u,int p,int x){
//		cout<<"modify "<<u<<' '<<L[u]<<' '<<R[u]<<' '<<p<<' '<<x<<endl;
		if(L[u]==R[u]){
			mx[u]=h[u]=x;
			return;
		}
		if(p<=R[ls(u)])
			modify(ls(u),p,x);
		else
			modify(rs(u),p,x);
		push_up(u);
	}
	
	void print(){
		for(int i=1;i<=n;i++)
			cout<<a[i]<<' ';
		cout<<endl;
	}
}ta,tb;


int main(){
	ios::sync_with_stdio(0);
	pb[0]=1;
	for(int i=1;i<=100000;i++)
		pb[i]=(ll)pb[i-1]*base%mod;
	
	cin>>ta.n;
	for(int i=1;i<=ta.n;i++)
		cin>>ta.a[i];
	cin>>tb.n;
	for(int i=1;i<=tb.n;i++)
		cin>>tb.a[i];
		
	ta.build(1,1,ta.n);
	tb.build(1,1,tb.n);
	
	cin>>m;
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			ta.modify(1,x,y);
//			ta.a[x]=y;
		}
		else if(op==2){
			tb.modify(1,x,y);
//			tb.a[x]=y;
		}
//		cout<<ta.cal(1,0).second<<' '<<tb.cal(1,0).second<<endl;
//		ta.print();tb.print();
		if(ta.cal(1,0).second==tb.cal(1,0).second)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 18428kb

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: -100
Wrong Answer
time: 55ms
memory: 18328kb

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:

YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
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...

result:

wrong answer 1st words differ - expected: 'NO', found: 'YES'