QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473829#6427. Just Another Game of StonesLinxWA 2912ms34388kbC++233.8kb2024-07-12 14:26:182024-07-12 14:26:19

Judging History

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

  • [2024-07-12 14:26:19]
  • 评测
  • 测评结果:WA
  • 用时:2912ms
  • 内存:34388kb
  • [2024-07-12 14:26:18]
  • 提交

answer

#include <bits/stdc++.h>
#define log(x) (31^__builtin_clz(x))
using namespace std;
const int maxn=2e5+5;
int n,q,a[maxn],op,l,r,x;
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;
}
const int maxm=500+5;
int bel[maxn],st[maxm],ed[maxm];
int Max[maxm];
bool vis[maxm];
int loc[maxm];
vector<int>qwq[maxm],Xor[maxm],sum[30][maxm];
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>a[i];
	int block=sqrt(n)+3;
	for(int i=1;i<=(n-1)/block+1;++i) {
		vis[i]=1;
		st[i]=(i-1)*block+1;
		ed[i]=min(i*block,n);
		for(int j=st[i];j<=ed[i];++j) {
			bel[j]=i;
			qwq[i].push_back(a[j]);
			Xor[i].push_back(0);
			for(int k=0;k<=29;++k) sum[k][i].push_back(0);
		}
		sort(qwq[i].begin(),qwq[i].end());
		for(int j=0;j<qwq[i].size();++j) {
			if(j==0) {
				Xor[i][j]=qwq[i][j];
				for(int k=0;k<=29;++k) sum[k][i][j]=((qwq[i][j]>>k)&1);
			}
			else {
				Xor[i][j]=(Xor[i][j-1]^qwq[i][j]);
				for(int k=0;k<=29;++k) sum[k][i][j]=((qwq[i][j]>>k)&1)+sum[k][i][j-1];
			}
		}
	}
	while(q--) {
		cin>>op>>l>>r>>x;
		if(op==1) {
			int s=bel[l]+1,t=bel[r]-1;
			for(int i=s;i<=t;++i) Max[i]=max(Max[i],x),vis[i]=1;
			vis[s-1]=vis[t+1]=1;
			for(int i=st[s-1];i<l;++i) {
				a[i]=max(a[i],Max[s-1]);
				//if(l<=i&&i<=r) a[i]=max(a[i],x);
				qwq[s-1][i-st[s-1]]=a[i];
			}
			for(int i=l;i<=ed[s-1];++i) {
				a[i]=max({a[i],Max[s-1],x});
				//if(l<=i&&i<=r) a[i]=max(a[i],x);
				qwq[s-1][i-st[s-1]]=a[i];
			}
			Max[s-1]=0;
			sort(qwq[s-1].begin(),qwq[s-1].end());
			for(int i=0;i<qwq[s-1].size();++i) {
				if(i==0) {
					Xor[s-1][i]=qwq[s-1][i];
					for(int k=0;k<=29;++k) sum[k][s-1][i]=((qwq[s-1][i]>>k)&1);
				}
				else {
					Xor[s-1][i]=(Xor[s-1][i-1]^qwq[s-1][i]);
					for(int k=0;k<=29;++k) sum[k][s-1][i]=((qwq[s-1][i]>>k)&1)+sum[k][s-1][i-1];
				}
			}
			if(bel[l]!=bel[r]) {
				for(int i=st[t+1];i<=r;++i) {
					a[i]=max({a[i],Max[t+1],x});
					//if(l<=i&&i<=r) a[i]=max(a[i],x);
					qwq[t+1][i-st[t+1]]=a[i];
				}
				for(int i=r+1;i<=ed[t+1];++i) {
					a[i]=max(a[i],Max[t+1]);
					//if(l<=i&&i<=r) a[i]=max(a[i],x);
					qwq[t+1][i-st[t+1]]=a[i];
				}
				Max[t+1]=0;
				sort(qwq[t+1].begin(),qwq[t+1].end());
				for(int i=0;i<qwq[t+1].size();++i) {
					if(i==0) {
						Xor[t+1][i]=qwq[t+1][i];
						for(int k=0;k<=29;++k) sum[k][t+1][i]=((qwq[t+1][i]>>k)&1);
					}
					else {
						Xor[t+1][i]=(Xor[t+1][i-1]^qwq[t+1][i]);
						for(int k=0;k<=29;++k) sum[k][t+1][i]=((qwq[t+1][i]>>k)&1)+sum[k][t+1][i-1];
					}
				}
			}
		}
		else {
			int s=bel[l]+1,t=bel[r]-1;
			int tmp=0;
			for(int i=s;i<=t;++i) {
				int p;
				if(vis[i])p=upper_bound(qwq[i].begin(),qwq[i].end(),Max[i])-qwq[i].begin();
				else p=loc[i];
				loc[i]=p;vis[i]=0;
				int len=qwq[i].size();
				tmp^=(Xor[i][len-1]^Xor[i][p-1]);
				if(p&1) tmp^=Max[i];
			}
			for(int i=l;i<=min(r,ed[s-1]);++i) tmp^=max(a[i],Max[s-1]);
			if(bel[l]!=bel[r]) {
				for(int i=st[t+1];i<=r;++i) tmp^=max(a[i],Max[t+1]);
			}
			tmp^=x;
			if(tmp==0) cout<<"0\n";
			else {
				int js=-1;
				int ans=0;
				if((tmp^x)<x) ans++;
				while(tmp) js++,tmp>>=1;
				for(int i=l;i<=min(r,ed[s-1]);++i) if((max(a[i],Max[s-1])&(1<<js))) ans++;
				if(bel[l]!=bel[r]) {
					for(int i=st[t+1];i<=r;++i) if((max(a[i],Max[t+1])&(1<<js))) ans++;
				}
				for(int i=s;i<=t;++i) {
					int p;
					if(vis[i])p=upper_bound(qwq[i].begin(),qwq[i].end(),Max[i])-qwq[i].begin();
					else p=loc[i];
					loc[i]=p;vis[i]=0;
					int len=qwq[i].size();
					if((Max[i]&(1<<js))) ans+=p;
					ans+=sum[js][i][len-1]-sum[js][i][p-1];
				}
				cout<<ans<<"\n";
			}
		}
	}
	return 0;
}

詳細信息

Test #1:

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

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: 0
Accepted
time: 2846ms
memory: 34296kb

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
19709
34617
138247
1211
755
16087
26119
14051
12263
33399
14363
41869
21117
97277
16733
64611
737
32715
25031
148859
17395
76263
56261
19825
93349
48429
22291
31645
9833
35195
95623
184389
39321
153
6067
6495
25369
9041
35785
39783
111237
151543
54289
121169
165785
101803
101821
15...

result:

ok 99837 numbers

Test #3:

score: 0
Accepted
time: 2867ms
memory: 34364kb

input:

200000 200000
962448218 958513200 826817273 288493295 72329606 793844396 161474258 749557053 862074728 135184207 668911451 838765519 576454286 121274388 388348135 263187992 907050448 15832750 818487193 381586607 465699121 602151844 79762183 196026513 582482566 931149307 480935730 159461747 585046007...

output:

18515
12719
24057
31925
17901
115925
146271
104061
8999
158211
146057
111579
31549
925
50509
62041
43485
3087
109093
6501
70803
59687
75457
137021
61153
24695
112325
3009
42565
14461
8419
2077
61229
60333
160819
40045
65745
4959
2349
13803
73683
115339
137585
48641
23943
1473
84973
68993
89153
5491
...

result:

ok 99962 numbers

Test #4:

score: 0
Accepted
time: 2848ms
memory: 34284kb

input:

200000 200000
962544405 669642056 644770364 502066363 533719237 13035646 395249287 167738631 464564098 211199761 1020133705 946182622 1029019688 608170888 436640902 723551797 834022694 136232881 822961515 47534172 334466005 1030545946 918761614 420047937 424153555 218369633 1035796657 306482436 1047...

output:

3255
81127
56879
67249
46421
116905
6071
4199
79925
17027
86579
891
62153
89905
97233
63251
10311
629
59525
142181
170519
3593
30971
86945
30873
81313
84145
3727
115629
1579
38801
6967
84659
134727
79203
108359
19231
116677
99273
12449
6909
189769
46489
77353
34309
13175
43589
124695
21251
35733
130...

result:

ok 99924 numbers

Test #5:

score: 0
Accepted
time: 2759ms
memory: 34360kb

input:

199999 200000
0 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 ...

output:

0
39093
0
0
7465
0
16579
0
14007
0
0
71337
0
0
0
52371
0
87361
0
21725
8205
0
0
0
0
8837
0
0
64937
0
0
0
62465
0
0
0
0
0
67977
107293
57805
83445
0
98381
0
101425
577
0
0
50485
31097
11921
37185
0
35729
11129
141839
121671
0
0
0
0
0
0
44997
0
0
0
132229
0
0
0
0
70937
0
78495
76809
31585
0
55525
1090...

result:

ok 99939 numbers

Test #6:

score: 0
Accepted
time: 2827ms
memory: 34324kb

input:

199999 199998
1514 307 1429 1644 257 1275 1599 1099 231 740 501 1730 30 1561 727 888 1148 152 373 1110 1776 917 304 1115 113 1254 383 1479 23 1954 462 916 1878 1432 1196 189 1274 477 26 1068 800 890 1554 1775 1777 1357 344 1551 1139 1469 168 584 1062 1181 1662 1430 452 1685 1468 565 635 1525 1767 15...

output:

75781
45269
14269
4339
54337
89997
105757
21133
47553
8351
95253
19225
2623
29671
48643
57371
22603
103747
176527
88497
118589
118351
61833
85051
110213
149685
29443
91475
6649
91685
2991
112405
14547
36451
509
107069
28719
8261
45761
9403
421
70013
3859
1619
51015
75363
19885
8387
112275
59989
8261...

result:

ok 100162 numbers

Test #7:

score: 0
Accepted
time: 2845ms
memory: 34208kb

input:

199997 199998
0 11 4 13 6 30 28 30 18 13 21 24 4 24 1 9 30 27 12 12 6 30 9 31 16 25 5 5 7 13 24 15 9 10 21 12 27 29 28 8 16 20 9 30 5 11 9 25 6 2 14 26 3 14 23 1 10 11 12 31 22 23 23 0 25 10 2 6 3 31 31 14 20 19 15 2 17 4 2 31 27 20 2 23 5 17 30 30 14 9 25 15 8 31 9 30 13 13 2 0 19 3 21 3 10 4 4 29 ...

output:

7875
57807
95059
7017
30085
5059
123909
151147
34203
40629
119345
20891
1495
23551
32049
5233
37025
33671
43355
107345
87053
44329
126053
31685
6605
42943
45281
39709
3877
15207
89705
138957
70835
64647
23691
94099
84845
138199
7169
122397
126567
92163
180731
106401
68389
87627
64683
66505
49689
320...

result:

ok 100039 numbers

Test #8:

score: 0
Accepted
time: 2849ms
memory: 34348kb

input:

200000 199999
4668 9598 10065 1023 4382 4541 16076 6223 325 7399 1681 11611 3915 12625 12012 3101 5877 10437 9827 4056 8839 7887 6919 6658 16307 4 2396 10023 7090 14603 4497 8402 11451 15937 12760 11208 1607 9783 12103 70 10618 14003 13963 225 7920 923 7255 13883 14042 7001 13603 6542 11491 5461 104...

output:

15847
73885
22405
26241
48215
49369
40595
22865
48395
1575
291
4075
77029
10367
73843
69795
52887
217
22145
85331
114429
24843
86459
83201
88993
743
49911
4483
123713
106695
19553
17135
83157
6279
60539
136965
78317
50811
116463
42387
71667
118363
75379
177487
25143
135211
17139
17189
102417
40571
2...

result:

ok 100009 numbers

Test #9:

score: 0
Accepted
time: 2865ms
memory: 34388kb

input:

199998 199999
142 205 18 177 86 154 20 205 121 127 136 164 89 198 108 17 193 107 206 25 224 255 143 214 119 49 32 14 164 92 204 139 23 155 224 250 86 71 153 190 198 16 102 22 202 192 148 228 129 200 52 244 74 54 140 195 146 111 185 99 115 176 123 151 92 68 39 101 60 45 49 85 44 225 137 42 32 99 22 1...

output:

61577
50809
20245
3463
46573
697
29129
81569
42515
57877
49169
82665
174741
65341
140177
13599
81267
21019
57693
136139
28817
76985
56417
80901
84037
21429
115749
110433
20955
73557
50325
68897
174761
134159
31961
91919
136631
29109
34579
153003
15239
89219
15355
22363
53619
23041
97471
45965
1143
6...

result:

ok 99994 numbers

Test #10:

score: 0
Accepted
time: 2787ms
memory: 34292kb

input:

199998 200000
3 0 2 1 1 3 0 0 3 2 3 2 1 3 0 3 0 0 0 3 0 2 2 1 3 1 0 2 3 3 1 2 1 0 3 1 2 3 1 1 3 1 3 0 0 1 2 3 0 0 2 2 3 0 1 0 2 3 1 0 3 2 1 3 0 2 2 1 3 1 3 1 3 2 0 2 3 0 0 0 3 0 0 2 1 0 1 2 2 1 3 3 0 1 2 1 1 1 2 3 0 3 1 3 2 2 1 1 2 2 1 3 2 3 3 2 0 0 1 2 2 1 2 2 1 1 3 1 1 3 1 1 0 0 3 1 3 2 0 1 3 0 1 ...

output:

56449
4915
71985
0
14371
0
0
0
11541
0
4637
42757
117321
0
62371
55519
57973
70817
8045
49393
86579
13985
67567
61477
24491
3035
0
0
109851
27473
94247
18935
67291
161183
0
25639
30009
0
62841
68297
19869
98727
15201
26151
18907
53265
0
99531
24917
0
30305
123295
56273
60597
51773
0
136061
29285
928...

result:

ok 99984 numbers

Test #11:

score: 0
Accepted
time: 2912ms
memory: 34352kb

input:

199996 199999
423 978 4050 3898 1965 1058 1152 2638 1557 2402 1592 2067 2356 3207 3276 3369 2275 4018 924 3298 2244 129 3412 2861 1659 2384 348 3873 264 1214 3470 2501 3570 3614 291 2340 3326 2634 1340 933 139 1985 2015 957 1666 601 3499 4023 3310 2013 3901 286 1945 3964 1521 1944 3295 2093 270 3268...

output:

6575
8081
6797
63763
75137
101097
45843
133997
5535
144715
38071
80853
14769
12365
17311
35777
47393
88781
29301
144099
13657
60523
79485
129717
29143
109805
12885
66583
79959
23397
12173
84345
83227
55747
146569
26455
73927
51239
38651
88431
42017
68795
22837
29077
65731
71843
126181
104623
59571
1...

result:

ok 100071 numbers

Test #12:

score: 0
Accepted
time: 2808ms
memory: 34352kb

input:

199999 199999
12 14 14 18 17 18 12 2 26 20 26 13 22 25 15 22 30 24 13 21 28 17 31 4 28 24 2 12 8 24 11 20 8 16 5 27 1 10 6 31 5 22 1 9 22 27 31 0 14 27 10 20 2 27 9 26 29 1 23 16 19 20 3 14 23 21 24 22 29 15 0 5 14 25 3 25 16 9 4 18 5 10 8 27 20 17 6 13 18 15 3 13 6 16 13 3 27 1 21 2 0 30 15 18 15 1...

output:

42389
23651
35637
43497
15619
76783
23709
58127
48189
44217
124433
30287
74693
50697
32599
87317
2917
24825
130475
47401
29545
94103
20077
126207
91967
169477
21031
59985
14139
124879
116201
114249
102707
53191
11817
46837
32709
62531
26469
35963
5567
155869
4559
32811
162027
8795
76991
118151
94243...

result:

ok 99941 numbers

Test #13:

score: -100
Wrong Answer
time: 2881ms
memory: 34288kb

input:

199997 200000
21267 22099 29656 6927 20364 29906 15775 15966 9409 22167 8072 12080 26203 25934 5819 18945 11587 17823 21070 16721 7222 2136 3505 18359 11310 31786 1449 27354 15914 7644 29348 22145 21420 5095 8717 5340 9444 234 1731 23278 9553 29647 19180 12463 734 17717 4219 2366 3571 6593 22961 601...

output:

18615
52241
102109
97415
146361
28759
7161
6431
21699
82941
22897
121947
54375
39853
22169
85437
140233
35401
88891
122477
125001
5331
174705
51625
83391
30551
122689
113755
50633
81111
74907
126349
178885
44513
137139
43139
8615
12451
106295
33699
49835
55055
97045
105695
38169
49257
30093
3347
120...

result:

wrong answer 95218th numbers differ - expected: '23987', found: '23997'