QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353641#8338. Quad Kingdoms ChessxuqinWA 6ms7956kbC++141.8kb2024-03-14 14:15:582024-03-14 14:16:00

Judging History

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

  • [2024-03-14 14:16:00]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:7956kb
  • [2024-03-14 14:15:58]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn=1e5+10;
const int inf=2e9, B=129313, mod=1000198943;

inline int read() {
	int x=0, f=1; char c=getchar();
	for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
	for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
	return f?x:-x; 
} 
int a[maxn], pw[maxn];

struct pj{	
	int val, mx, t;
	pj operator+(const pj& rhs) const{
		return (pj){(1LL*val*pw[rhs.t]%mod+rhs.val)%mod, max(mx, rhs.mx), t+rhs.t}; 
	}
};
struct segt{
	pj tr[maxn<<2], T[maxn<<2];
	pj merge(int u, int l, int r, int mx) {
		if(l==r) {
			if(tr[u].mx>=mx) return (pj){tr[u].mx, tr[u].mx, 1};
				else return (pj){0, 0, 0};
		}
		int mid=(l+r)>>1;
		if(tr[u<<1|1].mx>=mx) return T[u]+merge(u<<1|1, mid+1, r, mx);
			else return merge(u<<1, l, mid, mx);
	}
	void build(int u, int l, int r) {
		if(l==r) {
			tr[u]=(pj){a[l], a[l], 1};
			return;
		}
		int mid=(l+r)>>1;
		build(u<<1, l, mid); build(u<<1|1, mid+1, r);
		T[u]=merge(u<<1|1, l, mid, tr[u<<1|1].mx);
		tr[u]=T[u]+tr[u<<1|1];
	}
	void modify(int u, int l, int r, int k, int x) {
		if(l==r) {
			tr[u]=(pj){x, x, 1};
			return;
		}
		int mid=(l+r)>>1;
		if(k<=mid) modify(u<<1, l, mid, k, x);
			else modify(u<<1|1, mid+1, r, k, x);
		T[u]=merge(u<<1|1, l, mid, tr[u<<1|1].mx);
		tr[u]=T[u]+tr[u<<1|1];
	}
} AA, BB;
int main() {
	pw[0]=1;
	for(int i=1; i<=100000; ++i) pw[i]=1LL*pw[i-1]*B%mod;
	int n1=read();
	for(int i=1; i<=n1; ++i) a[i]=read();
	AA.build(1, 1, n1); 
	int n2=read();
	for(int i=1; i<=n2; ++i) a[i]=read();
	BB.build(1, 1, n2);
	
	int q=read();
	while(q--) {
		int ty=read(), p=read(), x=read();
		if(ty==1) AA.modify(1, 1, n1, p, x);
			else BB.modify(1, 1, n2, p, x);
		if(AA.tr[1].val==BB.tr[1].val) printf("YES\n");
			else puts("NO"); 
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7956kb

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: 6ms
memory: 5812kb

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
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 5th words differ - expected: 'YES', found: 'NO'