QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#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;
}

详细

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'