QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#276715	#4694. 异或序列	SoyTony	100 ✓	48ms	10892kb	C++14	1.5kb	2023-12-06 10:00:03	2023-12-06 10:00:04

Judging History

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

[2023-12-06 10:00:04]
评测

测评结果：100
用时：48ms
内存：10892kb

查看

[2023-12-06 10:00:03]
提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+10;
const int maxm=(1<<19)+10;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int n,m,k;
int sizb=320;
int a[maxn],b[maxn];
struct Query{
    int l,r,bel,id;
    bool operator<(const Query& rhs)const{
        if(bel==rhs.bel){
            if(bel&1) return r<rhs.r;
            else return r>rhs.r;
        }
        else return bel<rhs.bel;
    }
}q[maxn];

ll now,ans[maxn];
int cnta[maxm],cntb[maxm];
inline void addl(int x){
    ++cnta[a[x]],++cntb[b[x]];
    now+=cnta[k^b[x]];
}
inline void addr(int x){
    ++cnta[a[x]],++cntb[b[x]];
    now+=cntb[k^a[x]];
}
inline void dell(int x){
    now-=cnta[k^b[x]];
    --cnta[a[x]],--cntb[b[x]];
}
inline void delr(int x){
    now-=cntb[k^a[x]];
    --cnta[a[x]],--cntb[b[x]];
}

int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;++i){
        a[i]=read()^a[i-1];
        b[i]=a[i-1];
    }
    for(int i=1;i<=m;++i){
        q[i].l=read(),q[i].r=read();
        q[i].bel=(q[i].l-1)/sizb+1,q[i].id=i;
    }
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;++i){
        while(l>q[i].l) addl(--l);
        while(r<q[i].r) addr(++r);
        while(l<q[i].l) dell(l++);
        while(r>q[i].r) delr(r--);
        ans[q[i].id]=now;
    }
    for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 10

Accepted

time: 2ms

memory: 9892kb

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:

result:

ok 1000 numbers

Test #2:

score: 10

Accepted

time: 0ms

memory: 7932kb

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:

result:

ok 1000 numbers

Test #3:

score: 10

Accepted

time: 0ms

memory: 7848kb

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:

result:

ok 1000 numbers

Test #4:

score: 10

Accepted

time: 41ms

memory: 10776kb

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:

result:

ok 100000 numbers

Test #5:

score: 10

Accepted

time: 42ms

memory: 10060kb

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:

result:

ok 100000 numbers

Test #6:

score: 10

Accepted

time: 41ms

memory: 10604kb

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:

result:

ok 100000 numbers

Test #7:

score: 10

Accepted

time: 48ms

memory: 9004kb

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:

result:

ok 100000 numbers

Test #8:

score: 10

Accepted

time: 44ms

memory: 10892kb

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:

result:

ok 100000 numbers

Test #9:

score: 10

Accepted

time: 44ms

memory: 9660kb

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:

result:

ok 100000 numbers

Test #10:

score: 10

Accepted

time: 44ms

memory: 10556kb

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