QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #67500 | #4694. 异或序列 | alpha1022 | 100 ✓ | 100ms | 3960kb | C++23 | 1.5kb | 2022-12-10 16:39:54 | 2022-12-10 16:39:57 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,k,f[100010],block,pos[100010],cnt[200010],cur;
struct s_query
{
int l,r,id,ans;
} qry[100010];
bool comp(const s_query &a,const s_query &b)
{
return pos[a.l] < pos[b.l] || (pos[a.l] == pos[b.l] && a.r < b.r);
}
bool comp2(const s_query &a,const s_query &b)
{
return a.id < b.id;
}
void update(int x,int opt)
{
if(opt == 1)
{
cur += cnt[f[x] ^ k];
++cnt[f[x]];
}
else
{
--cnt[f[x]];
cur -= cnt[f[x] ^ k];
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
block = sqrt(n);
for(register int i = 1;i <= n;++i)
scanf("%d",f + i),pos[i] = (i - 1) / block + 1,f[i] ^= f[i - 1];
cnt[0] = 1;
for(register int i = 1;i <= m;++i)
scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
sort(qry + 1,qry + m + 1,comp);
register int l = 1,r = 0;
for(register int i = 1;i <= m;++i)
{
//printf("\nQuery %d:\n",i);
while(r < qry[i].r) update(++r,1);
//printf("1:%d %d\n",l,r);
while(r > qry[i].r) update(r--,0);
//printf("2:%d %d\n",l,r);
while(l < qry[i].l) update(l - 1,0),++l;
//printf("3:%d %d\n",l,r);
while(l > qry[i].l) --l,update(l - 1,1);
//printf("4:%d %d\n",l,r);
//printf("%d\n",i);
qry[i].ans = cur;
}
sort(qry + 1,qry + m + 1,comp2);
for(register int i = 1;i <= m;++i)
printf("%d\n",qry[i].ans);
}
详细
Test #1:
score: 10
Accepted
time: 2ms
memory: 1664kb
input:
1000 1000 85 96 4 38 13 19 27 85 1 56 79 33 34 85 74 37 58 30 78 97 94 12 85 58 65 61 99 34 47 1 18 36 14 43 50 86 84 9 65 90 3 26 96 76 58 56 41 7 33 99 92 88 75 94 0 89 82 83 19 51 10 67 12 24 98 17 72 21 45 33 87 19 68 62 43 99 95 15 79 22 19 93 86 81 58 90 9 2 49 50 82 56 74 78 26 63 70 10 31 29...
output:
213 1400 792 6 231 3800 232 2102 3776 1737 277 147 2197 2405 1444 2026 3698 190 88 68 87 64 19 410 84 1446 81 3660 836 675 602 1062 3644 2114 2200 432 1461 13 1569 869 1075 990 1701 253 224 778 3801 3742 422 21 2386 256 3816 2678 2063 1201 17 3099 180 10 835 3342 1246 416 41 142 525 2056 3541 2180 1...
result:
ok 1000 numbers
Test #2:
score: 10
Accepted
time: 1ms
memory: 1640kb
input:
1000 1000 78 47 78 80 30 47 83 7 25 94 39 68 89 43 87 81 78 1 85 85 38 90 23 48 52 28 0 56 31 13 68 57 49 76 87 0 52 60 33 16 36 1 3 87 20 11 60 63 39 89 38 82 67 97 32 99 58 34 36 48 35 1 63 0 44 64 95 60 64 0 36 85 80 96 25 32 79 79 1 0 51 46 57 27 88 42 51 45 45 99 41 33 16 43 74 44 54 20 93 85 8...
output:
3103 2051 2244 410 604 950 292 2856 572 2544 25 772 2438 340 548 2046 1317 671 3421 3762 1982 110 485 3167 14 3664 2691 1893 1932 3161 122 895 36 1468 2327 1229 3668 511 2131 2971 1029 1 228 432 922 45 1738 79 1126 3 1789 1119 2207 1539 1931 2958 3232 525 3277 162 423 137 1173 725 421 1735 0 1594 31...
result:
ok 1000 numbers
Test #3:
score: 10
Accepted
time: 1ms
memory: 1664kb
input:
1000 1000 45 10 49 1 30 67 94 36 99 22 8 3 93 92 81 94 29 50 54 4 57 90 69 64 64 71 13 85 3 59 24 21 56 50 55 55 15 34 25 46 98 26 94 61 69 50 92 86 88 82 77 98 50 96 69 30 25 9 65 38 16 17 2 26 18 27 67 55 78 20 97 75 50 95 60 89 28 42 84 47 71 54 6 19 17 1 14 80 69 36 57 78 3 8 3 42 26 69 53 25 32...
output:
70 911 3713 41 1817 3110 3037 11 2525 440 50 939 1572 502 1414 544 521 162 63 2464 579 281 2380 649 2675 183 1040 391 3119 2562 2492 3490 1660 2768 408 2 523 979 2743 2687 2558 1447 5 24 24 3078 1789 790 3423 316 702 3727 2020 1795 35 1237 3443 4 782 3187 141 149 16 124 2808 5 678 995 89 3763 3004 1...
result:
ok 1000 numbers
Test #4:
score: 10
Accepted
time: 73ms
memory: 3880kb
input:
100000 100000 20 85 22 35 80 21 40 71 12 44 76 93 10 53 96 22 48 16 22 79 64 94 81 92 63 2 86 50 35 95 76 13 62 71 77 61 29 60 37 10 44 22 56 62 9 44 31 65 32 15 38 36 33 37 14 41 26 48 42 94 99 50 98 66 33 47 92 53 10 61 83 68 13 94 38 17 94 35 51 55 63 13 13 70 64 68 11 64 69 37 93 58 32 29 37 91 ...
output:
17058042 1471792 7796685 345472 627482 487686 11170882 848131 25589667 12305593 19955501 35829333 11325552 6722842 12598811 15518980 16435869 13128933 3753218 5938962 3044641 6834473 13841 1438243 12789761 20970750 174212 3990695 1195194 58984 140029 379645 4697080 33714911 33875292 25060447 9041621...
result:
ok 100000 numbers
Test #5:
score: 10
Accepted
time: 84ms
memory: 3912kb
input:
100000 100000 18 66 55 3 33 54 21 44 15 41 68 30 80 53 32 97 54 75 14 18 97 94 58 8 91 44 2 64 50 25 93 88 20 27 69 84 51 4 32 30 19 66 4 24 21 98 39 92 91 63 63 93 76 96 39 8 30 51 74 7 66 48 58 63 83 57 13 95 26 0 76 34 99 88 81 22 47 57 12 85 8 71 25 18 49 14 33 66 25 62 56 35 22 4 16 56 26 52 25...
output:
414024 21993318 7014055 263251 32250161 34246168 22577232 1023991 29794048 29073686 28771989 3160122 1763604 2716889 4345665 30268491 3664970 13775298 37160 28000564 5064446 26537196 6174521 29108627 14674072 20970932 843604 3961040 541796 4727815 8521536 847052 22282320 36408859 33977062 16555458 3...
result:
ok 100000 numbers
Test #6:
score: 10
Accepted
time: 79ms
memory: 3872kb
input:
100000 100000 81 60 30 90 68 8 70 17 40 46 87 80 32 31 15 89 15 36 86 79 36 33 57 45 55 6 46 84 6 58 43 93 34 30 77 40 80 16 20 78 28 38 12 19 4 56 9 35 43 88 43 82 54 51 63 24 58 39 68 87 88 54 64 38 69 99 12 20 55 97 23 22 20 29 31 60 91 81 8 77 14 70 86 98 26 87 49 73 61 68 54 1 26 54 2 21 82 9 2...
output:
4140552 17719673 38402973 1665112 19237792 9674217 19802284 12834714 6181148 36807 149262 4067408 20216257 14447448 3368541 23373945 13864102 259380 31037191 6951570 11174612 31941387 33960223 119052 29429635 47669 5758749 663454 14285575 548422 12030018 33682352 4550912 198195 4555632 1718069 67749...
result:
ok 100000 numbers
Test #7:
score: 10
Accepted
time: 78ms
memory: 3952kb
input:
100000 100000 68 87 66 22 64 37 80 46 67 29 75 58 6 59 88 25 6 78 21 77 60 46 98 96 70 25 17 13 63 30 81 2 9 83 30 35 97 68 79 34 5 63 62 38 20 60 35 74 80 79 80 62 12 38 93 85 2 83 59 16 51 73 86 11 83 32 52 60 70 9 1 91 91 76 9 41 88 63 76 49 31 42 75 23 31 60 44 74 25 47 92 80 26 29 6 82 39 28 67...
output:
13644517 27109340 19539605 15080023 2011048 1636623 10793001 92116 36837863 25586776 10186029 29260745 23747542 22588808 26552928 23586056 5547914 15298794 283941 25609745 929305 7682623 31878505 33152181 13562198 27970116 26439747 4951956 53705 28589066 3287 32760626 4505854 550753 8921778 3557173 ...
result:
ok 100000 numbers
Test #8:
score: 10
Accepted
time: 81ms
memory: 3928kb
input:
100000 100000 87 26 96 32 51 73 81 8 94 30 73 40 12 73 20 53 48 71 72 87 82 55 81 13 32 63 53 22 6 61 25 33 25 75 36 61 70 37 23 9 56 35 32 39 48 78 94 16 43 19 86 40 60 51 67 21 34 63 17 20 20 19 96 84 48 57 73 49 94 76 44 86 98 92 91 3 7 28 90 11 28 46 21 23 62 5 65 31 93 8 0 89 29 0 20 46 82 52 2...
output:
16035378 1530014 13851011 4832560 15843123 3576067 1000485 342706 28711970 2053699 33544303 8410810 12966788 23416550 33617380 1530480 4068185 18821476 12352328 932430 12806970 1154337 7852624 12473544 31269460 4573278 21553441 3628854 24606589 16561716 6423281 165541 29113924 6056003 12645150 10843...
result:
ok 100000 numbers
Test #9:
score: 10
Accepted
time: 85ms
memory: 3856kb
input:
100000 100000 239 855 955 421 138 936 218 288 694 256 655 187 614 738 58 668 292 315 554 725 285 664 618 867 182 205 129 302 677 246 466 100 987 893 327 385 933 785 75 707 45 935 658 266 80 957 268 388 557 419 353 649 725 765 504 579 52 115 46 334 761 802 467 384 892 219 675 296 504 170 726 544 888 ...
output:
1376788 2636 1770560 701056 2238950 841993 261662 1796744 4452646 3957740 579707 2739680 564754 847630 2883013 1989903 3762807 2946255 92425 2530068 94124 2796338 1014066 1057726 1311233 3249782 37485 860678 3728953 4862154 1184446 508348 4339573 1488440 25270 3898602 3287961 320658 2146252 339398 2...
result:
ok 100000 numbers
Test #10:
score: 10
Accepted
time: 100ms
memory: 3960kb
input:
100000 100000 15 75 47 70 77 61 57 79 92 78 39 6 39 41 68 71 15 87 85 35 0 90 23 53 31 1 2 93 76 60 25 96 26 43 35 99 45 92 51 99 77 35 63 42 47 58 12 92 72 53 49 5 45 80 45 34 36 6 96 85 20 89 98 33 64 75 87 34 18 8 42 16 44 56 57 65 71 72 49 46 47 22 37 86 42 44 44 6 9 12 5 34 2 34 34 22 52 59 30 ...
output:
9298745 24142958 4041701 1903815 34893833 731340 9814237 11498184 32036895 3264042 382146 2326417 24172772 14466434 166865 6113688 10495266 28351180 25262495 60000 12335709 7208927 14881 24429821 33043874 3671602 12862 29767499 33658665 1045449 621224 530778 10992444 8936337 4618931 5065243 14080617...
result:
ok 100000 numbers