QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53132#4808. Great PartySilent_AshWA 3ms6256kbC++1.8kb2022-10-04 19:01:182022-10-04 19:01:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-04 19:01:22]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:6256kb
  • [2022-10-04 19:01:18]
  • 提交

answer

#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll ;
const int N = 1e6 + 5 ;
const int BIT = 1 << 17 ;

int rd()
{
	int res = 0 , f = 1 ;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f = -1 ; ch = getchar() ;}
	while(ch >= '0' && ch <= '9')res = (res << 1) + (res << 3) + (ch ^ 48) , ch = getchar() ;
	return res * f ;
}

int n , q , sq ;

struct Q
{
	int l , r , p ;
	Q(){}
	Q(int a , int b , int c):l(a),r(b),p(c){};
	bool operator < (Q q) const
	{
		if(l / sq != q.l / sq) return l / sq < q.l / sq ;
		return r > q.r ;
	}
	~Q(){}
}que[N] ;

int a[N] , pre[N] , ans[N] ;

int cnt[N * 5] , sum , l = 1 , r ;
int C2(int n){return n / 2.0 * (n - 1) ;}

void del(int p)
{
	sum -= C2(cnt[pre[p]]--) ;
	sum += C2(cnt[pre[p]]) ;
}

void add(int p)
{
	sum -= C2(cnt[pre[p]]++) ;
	sum += C2(cnt[pre[p]]) ;
}

int query(int ql , int qr)
{
	while(l > ql) add(--l) ;
	while(r < qr) add(++r) ;
	while(l < ql) del(l++) ;
	while(r > qr) del(r--) ;
	return sum ;
}

int main()
{
	n = rd() ; q = rd() ; sq = sqrt(n) ;
//	for(int i = 1 ; i <= n ; i++)
//		a[i] = rd() ;
	for(int i = 1 ; i <= n ; i++)
		pre[i] = pre[i - 1] ^ (rd() - 1 | BIT) ;
		
	for(int i = 1 ; i <= q ; i++)
	{
		int a = rd() - 1 , b = rd() ;
		que[i] = Q(a , b , i) ;
	}
//	for(int i = 1 ; i <= q ; i++)
//		que[i] = Q(rd() - 1 , rd() , i) ;
	sort(que + 1 , que + 1 + q) ;
	
	for(int i = 1 ; i <= q ; i++)
//		cout << que[i].l << ' ' << que[i].r << ' ' << que[i].p << '\n' ,
		ans[que[i].p] = C2(que[i].r - que[i].l + 1) - query(que[i].l , que[i].r) ;
	for(int i = 1 ; i <= q ; i++)
		cout << ans[i] << '\n' ;
	return 0;
}


详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3584kb

input:

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

output:

3
2
3
5
5

result:

ok 5 number(s): "3 2 3 5 5"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

4 5
5 6 7 8
1 2
2 3
3 4
1 3
2 4

output:

3
3
3
6
6

result:

ok 5 number(s): "3 3 3 6 6"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

10 10
3 7 3 1 6 6 10 3 3 3
9 10
5 10
3 7
5 6
5 6
9 10
3 10
1 4
6 6
1 4

output:

2
18
14
2
2
2
33
10
1
10

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

10 8
91 63 1 34 50 11 10 73 96 67
5 9
2 7
2 5
4 7
1 10
3 3
1 4
5 10

output:

15
21
10
10
55
1
10
21

result:

ok 8 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 3712kb

input:

10 6
9 539 285 408 615 861 951 413 319 368
4 4
8 10
1 7
3 9
2 3
2 10

output:

1
6
28
28
3
45

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 3628kb

input:

10 6
1348 7002 4687 6325 8253 5750 2464 5509 6543 8704
3 9
4 8
8 8
8 9
2 9
9 10

output:

28
15
1
3
36
3

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

10 8
59041 28802 92255 14246 65768 79252 70656 81265 98363 85237
1 6
9 10
4 7
6 8
9 10
1 2
1 3
4 5

output:

21
3
10
6
3
3
6
3

result:

ok 8 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10 7
28607 249948 373828 584253 989446 308313 199311 253174 283937 133758
2 4
1 2
4 9
7 8
7 8
2 6
1 1

output:

6
3
21
3
3
15
1

result:

ok 7 numbers

Test #9:

score: 0
Accepted
time: 2ms
memory: 3684kb

input:

100 98
6 9 6 10 8 10 3 4 7 5 4 10 2 10 4 5 2 1 7 1 3 1 4 1 1 2 6 9 3 10 2 5 3 2 6 2 1 7 7 6 5 4 2 5 3 2 7 2 6 2 9 7 10 7 4 2 9 3 3 7 9 1 4 9 6 1 5 5 8 3 7 5 8 3 9 5 8 7 8 6 6 3 2 3 8 1 8 1 5 9 1 8 6 3 3 7 10 6 5 5
48 72
14 46
23 28
37 84
1 65
45 72
9 19
9 81
37 53
47 50
25 26
26 88
51 54
53 69
22 94...

output:

316
534
20
1144
2054
394
64
2596
149
10
3
1944
10
148
2598
35
169
6
28
318
605
2964
366
4571
2815
130
1220
52
160
2964
129
3040
793
1491
89
1932
227
64
77
420
332
646
267
1081
902
956
2668
2191
449
149
223
5
3763
1312
102
1221
578
2188
289
681
367
960
1
226
151
720
116
101
3348
905
132
1
88
1140
199...

result:

ok 98 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 3600kb

input:

100 96
78 64 64 32 42 65 94 54 35 27 83 6 6 90 86 45 93 72 56 80 5 31 91 87 56 10 100 79 53 69 98 93 79 28 89 5 14 4 12 100 50 98 99 6 29 38 85 37 34 85 15 76 73 7 91 93 28 10 74 23 96 77 27 84 21 79 62 69 14 81 18 93 1 23 11 1 13 72 8 91 11 45 50 67 21 42 55 44 95 57 4 85 17 96 84 46 22 56 19 58
1 ...

output:

2761
1029
4167
3989
28
90
626
625
2614
494
942
626
253
2200
171
3389
250
4539
251
941
558
55
3308
251
1372
349
55
662
2688
737
378
66
699
136
2335
44
90
151
856
626
1270
45
1121
815
406
1477
77
228
525
1760
45
210
629
2070
66
1760
9
463
15
1220
557
591
190
699
463
28
816
1076
118
44
492
44
1942
2616...

result:

ok 96 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

100 98
354 899 868 821 878 486 413 896 872 129 97 801 838 279 971 756 250 24 245 883 731 887 106 204 381 204 678 33 340 987 80 662 845 955 39 654 989 24 105 822 704 690 573 800 243 372 939 338 986 246 983 445 196 931 290 150 610 635 809 496 779 722 596 920 67 16 391 728 575 975 469 413 82 768 680 43...

output:

21
741
21
253
1275
325
465
703
3
276
105
495
465
3
136
1224
1652
1
66
780
253
1225
2484
55
1484
120
528
1175
1484
45
300
496
1378
3239
465
1
190
630
2850
1830
1952
325
3
1
36
1325
153
435
231
1225
406
6
153
465
28
105
351
666
1769
253
2211
1891
819
406
2345
496
1830
21
528
300
2628
10
2016
6
1710
10...

result:

ok 98 numbers

Test #12:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

100 98
4940 7560 6878 1066 6510 7648 7900 5423 1384 5142 6451 2335 6486 5411 5312 3059 1974 7844 4678 9963 926 8585 6379 1352 179 919 4870 3315 1907 8327 519 9396 1628 9268 7695 9932 9154 1056 2772 3916 4397 5712 5614 7771 2968 6540 6205 2692 6900 3920 6688 2278 7843 7293 8751 5538 2638 6424 5234 27...

output:

861
351
528
2415
21
1176
2278
78
3
45
465
903
55
1035
45
171
190
120
2145
105
3
465
28
703
3570
210
66
3081
861
561
15
1081
2145
3
3
91
378
210
15
630
1596
666
990
703
66
55
45
820
55
1431
465
4186
78
276
153
136
3
231
2556
861
666
1540
300
15
15
325
2016
1128
2415
105
2850
496
55
55
1225
1770
780
2...

result:

ok 98 numbers

Test #13:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

100 98
79873 84742 75872 96693 10191 985 31311 53705 98909 81177 17919 79656 53853 81691 50226 50507 73858 61819 29518 85453 34982 53653 93823 31917 3269 21003 95730 52976 65728 25570 21628 88764 20155 36740 90961 65470 511 72479 12397 89701 31897 5413 84398 51940 52729 43338 40696 80980 67508 12297...

output:

2850
276
210
91
1891
1081
3
2485
946
2850
10
136
465
28
136
36
3741
496
1176
55
1378
45
45
465
105
2485
3
741
465
1596
1225
136
1891
1225
1378
231
351
3081
136
861
946
2278
45
1953
171
406
6
21
703
105
3570
6
91
703
1891
4278
741
105
210
1225
990
435
3828
66
1540
2080
91
3160
66
946
351
55
28
1378
2...

result:

ok 98 numbers

Test #14:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

100 97
870479 594266 17979 445914 279977 701082 808468 978143 124772 925808 486496 725792 13151 914792 840639 180601 194842 81935 895414 306762 943164 688186 185644 68600 41614 718973 668908 952621 806142 891060 222118 647764 302429 649853 411693 527647 102818 427196 466555 290753 496356 16854 65968...

output:

171
2016
1081
6
3
465
2278
1
2775
3570
703
36
1378
595
15
15
36
2016
4095
45
36
1128
630
3403
406
741
36
1830
1770
21
1711
1081
153
2926
2701
780
136
595
91
595
2926
210
15
36
1485
171
325
903
171
528
351
2628
1711
300
435
2775
190
78
3
1540
6
10
903
10
820
15
2278
2926
91
2346
496
210
1035
3655
122...

result:

ok 97 numbers

Test #15:

score: 0
Accepted
time: 3ms
memory: 3728kb

input:

1000 998
7 7 4 6 4 2 1 1 4 6 7 8 8 6 2 7 8 8 5 4 9 1 1 9 6 6 9 5 3 3 10 3 9 6 9 10 2 8 8 2 7 8 3 7 6 4 7 5 9 3 7 1 4 8 3 9 1 1 3 6 10 5 7 3 5 3 9 5 10 9 3 2 9 10 9 7 4 7 5 6 6 6 4 5 2 10 8 2 9 8 7 10 5 2 4 9 7 4 6 9 9 7 3 1 5 3 6 2 6 1 2 6 4 6 8 7 10 2 1 3 2 10 8 5 2 8 2 9 8 3 1 1 4 3 1 2 9 8 2 2 2 ...

output:

52639
55406
72778
54893
31854
3069
4317
385800
65839
83181
191315
12145
14934
27816
39539
80779
151139
242323
57860
14575
225042
8888
9297
130307
106835
20703
71224
46746
4052
2153
101782
16162
2619
2957
31847
145806
174061
63334
173537
124849
6000
38902
14911
17210
104593
14245
96191
41493
47304
73...

result:

ok 998 numbers

Test #16:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

1000 996
51 45 23 20 19 16 22 67 57 30 61 32 80 46 38 76 62 6 22 74 7 25 20 16 70 78 100 47 39 39 17 63 46 2 11 28 75 51 58 47 12 32 66 62 7 8 57 59 100 29 32 81 11 90 26 16 88 57 39 52 10 6 94 5 93 70 67 26 75 37 6 98 51 88 11 29 97 28 36 41 63 62 66 82 8 32 52 17 95 46 14 2 60 51 15 54 20 80 63 78...

output:

2402
70241
57082
16389
460411
87228
24207
6081
29295
464
23109
1029
76305
816
21438
281265
5750
28316
24211
209
20626
70231
67599
16767
76337
75565
95332
69830
79912
23995
104667
156491
1704
8737
115967
173075
191139
26702
9830
363626
147079
54719
402035
75144
126292
1426
36965
114954
395816
23565
8...

result:

ok 996 numbers

Test #17:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

1000 1000
646 746 291 354 931 823 84 484 142 439 893 10 999 669 753 794 503 753 459 997 46 375 445 106 365 862 458 833 445 387 76 536 430 347 87 577 649 308 764 674 799 229 623 259 159 105 385 108 380 808 79 149 972 318 377 260 555 835 915 882 542 73 647 190 864 41 850 361 937 318 659 392 18 15 279 ...

output:

1430
147618
3569
106439
56590
12244
189327
6782
5250
7996
32359
122703
4464
84206
11320
210
265961
45
40450
33914
29383
19295
45
20296
171310
350
5050
5459
2413
2483
313084
55
6104
4003
3399
14019
28190
37926
230743
73497
199922
7136
28
60348
49120
3485
5993
18903
39035
78159
1225
2016
90473
3398
18...

result:

ok 1000 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

1000 996
8525 156 5909 2878 6958 7610 1178 9088 2285 9626 2329 4812 7629 3037 137 9397 6502 8279 1731 3105 9715 1633 2117 3898 3588 7368 3409 8272 8877 7020 3515 6534 4005 4434 2286 1872 4184 3778 1591 3435 6662 5849 9512 2133 9650 6969 7399 2641 2915 8740 1741 7508 5142 725 2919 795 7227 951 5816 4...

output:

2774
314807
102376
102828
67160
946
9180
45147
7260
95701
22363
130298
296058
189413
434
178495
496
3321
74688
210269
415402
4465
3239
27729
147148
365073
51678
51357
214833
153731
53299
206396
10
165594
4753
861
207037
41038
595
13203
22578
9453
5565
216144
1325
5886
38501
232896
239076
44549
64976...

result:

ok 996 numbers

Test #19:

score: 0
Accepted
time: 1ms
memory: 4552kb

input:

1000 1000
84503 47470 36151 1858 36249 70169 49861 23790 35769 8439 88417 71033 66247 75932 99021 37885 31352 95044 12591 22229 15973 34090 89843 90849 8105 73586 21126 71812 99271 37888 96412 10917 90177 97694 61228 93073 38114 5338 45007 34968 34005 30117 13124 52363 78732 62645 91983 28612 59738 ...

output:

14365
8911
103284
419068
177308
400063
27028
24090
113049
23871
108810
147152
61775
19701
70124
185743
8385
13203
18720
94394
32640
294527
116402
1377
61075
18145
6105
181501
14364
230179
229501
51680
38781
27028
223445
12561
9180
35510
946
13202
77814
30134
120
64619
4753
227474
26796
9180
51360
22...

result:

ok 1000 numbers

Test #20:

score: -100
Wrong Answer
time: 2ms
memory: 6256kb

input:

1000 996
746942 404907 332060 103389 714995 191748 291638 567887 616738 977031 744755 722024 161175 130095 536035 832948 690949 949370 585465 522053 135872 80107 410575 81582 350148 701001 893405 945609 218476 156318 980102 679602 305916 69753 993868 58954 182232 838189 163478 207221 773514 775184 3...

output:

55610
225455
225455
96579
125249
123751
15225
17766
105
25425
106029
18721
1081
46056
194375
44849
42778
4186
28441
10878
9870
8911
93960
162164
138600
213529
21736
9045
38781
136502
155960
15753
1431
1891
2850
2628
91
7021
247454
6441
23004
13694
4950
5151
33930
408153
348193
1176
4560
8911
259558
...

result:

wrong answer 1st numbers differ - expected: '55611', found: '55610'