QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53132 | #4808. Great Party | Silent_Ash | WA | 3ms | 6256kb | C++ | 1.8kb | 2022-10-04 19:01:18 | 2022-10-04 19:01:22 |
Judging History
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'