QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474031#6427. Just Another Game of StonesLinxWA 82ms83388kbC++232.7kb2024-07-12 15:38:592024-07-12 15:38:59

Judging History

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

  • [2024-07-12 15:38:59]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:83388kb
  • [2024-07-12 15:38:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int Inf=0x3f3f3f3f;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,q,a[maxn],op,l,r,x;
struct Node{
	int l,r,sum,Min,se,cnt;
	int lazy;
	int js[30];
}tree[maxn<<2];
void pushup(int rt) {
	tree[rt].Min=min(tree[rt<<1].Min,tree[rt<<1|1].Min);
	if(tree[rt<<1].Min==tree[rt<<1|1].Min) {
		tree[rt].se=min(tree[rt<<1].se,tree[rt<<1|1].se);
		tree[rt].cnt=tree[rt<<1].cnt+tree[rt<<1|1].cnt;
	}
	else if(tree[rt<<1].Min<tree[rt<<1|1].Min) {
		tree[rt].se=min(tree[rt<<1].se,tree[rt<<1|1].Min);
		tree[rt].cnt=tree[rt<<1].cnt;
	}
	else {
		tree[rt].se=min(tree[rt<<1].Min,tree[rt<<1|1].se);
		tree[rt].cnt=tree[rt<<1|1].cnt;
	}
	tree[rt].sum=(tree[rt<<1].sum^tree[rt<<1|1].sum);
	for(int k=0;k<=29;++k) tree[rt].js[k]=tree[rt<<1].js[k]+tree[rt<<1|1].js[k];
}
void build(int rt,int l,int r) {
	tree[rt].l=l,tree[rt].r=r;
	if(l==r) {
		tree[rt].sum=a[l];
		tree[rt].Min=a[l];
		tree[rt].cnt=1;
		tree[rt].se=Inf;
		for(int k=0;k<=29;++k) tree[rt].js[k]=((a[l]>>k)&1);
		return;
	}
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}
void update(int rt,int x) {
	if(tree[rt].cnt&1) tree[rt].sum^=(tree[rt].Min^x);
	for(int k=0;k<=29;++k) {
		if((tree[rt].Min>>k)&1) tree[rt].js[k]-=tree[rt].cnt;
		if((x>>k)&1) tree[rt].js[k]+=tree[rt].cnt;
	}
	tree[rt].Min=x;
	tree[rt].lazy=max(tree[rt].lazy,x);
}
void pushdown(int rt) {
	if(tree[rt].lazy) {
		update(rt<<1,tree[rt].lazy);
		update(rt<<1|1,tree[rt].lazy);
		tree[rt].lazy=0;
	}
}
void update_max(int rt,int l,int r,int L,int R,int x) {
	if(L>r||R<l||x<=tree[rt].Min) return;
	if(L<=l&&R>=r&&x<tree[rt].se) {
		update(rt,x);
		return;
	}
	if(l==r)exit(0);
	pushdown(rt);
	int mid=l+r>>1;
	update_max(rt<<1,l,mid,L,R,x);
	update_max(rt<<1|1,mid+1,r,L,R,x);
	pushup(rt);
}
int Xor,sum[30];
void query(int rt,int l,int r,int L,int R) {
	if(R<l||L>r) return;
	if(L<=l&&R>=r) {
		for(int k=0;k<=29;++k) sum[k]+=tree[rt].js[k];
		Xor^=tree[rt].sum;
		return;
	}
	pushdown(rt);
	int mid=l+r>>1;
	query(rt<<1,l,mid,L,R);
	query(rt<<1|1,mid+1,r,L,R);
	return;
}
int main() {
	n=read(),q=read();
	for(int i=1;i<=n;++i) a[i]=read();
	build(1,1,n);
	while(q--) {
		op=read(),l=read(),r=read(),x=read();
		if(op==1) update_max(1,1,n,l,r,x);
		else {
			Xor=0;
			for(int k=0;k<=29;++k) sum[k]=0;
			query(1,1,n,l,r);
			Xor^=x;
			int ans=0;
			if((Xor^x)<x) ans++;
			int p=-1;
			while(Xor) p++,Xor>>=1;
			printf("%d\n",ans+sum[p]);
		}
	}
	return 0;
}

详细

Test #1:

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

input:

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

output:

1
0
3

result:

ok 3 number(s): "1 0 3"

Test #2:

score: -100
Wrong Answer
time: 82ms
memory: 83388kb

input:

200000 200000
962352030 173642520 1008864183 74920228 684681800 500911321 1001441054 257633652 185843534 59168654 317689197 731348417 123888883 708119712 340055368 876566011 980078202 969174443 814012870 715639041 596932238 173757742 314504576 1045746913 740811577 570187156 999816627 12441059 122507...

output:

38889
57353
46659
19851
34617
128539
1097
621
16087
24597
14051
12263
33399
14363
41869
21117
97277
16733
64611
737
32715
25031
148859
17395
76263
56261
19825
93349
48529
22291
31645
9833
35133
95623
184311
39321
2619
6067
12315
25369
9041
35785
39783
111237
151543
54289
121169
165785
101803
172387
...

result:

wrong answer 4th numbers differ - expected: '19709', found: '19851'