QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#291159	#4694. 异或序列	MoRanSky	100 ✓	49ms	7036kb	C++23	1.2kb	2023-12-26 05:08:23	2023-12-26 05:08:23

Judging History

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

[2023-12-26 05:08:23]
评测

测评结果：100
用时：49ms
内存：7036kb

查看

[2023-12-26 05:08:23]
提交

answer

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 100005;

typedef long long LL;

int n, m, t, K, a[N], pos[N], cnt[N];

LL res = 0, ans[N];

struct Q{
	int l, r, id;
	bool operator < (const Q &b) const {
		if (pos[l] != pos[b.l]) return pos[l] < pos[b.l];
		return (pos[l] & 1) ? r < b.r : r > b.r;
	}
} q[N];

void inline add(int x) {
	res += cnt[x ^ K];
	cnt[x]++;
}

void inline del(int x) {
	res -= cnt[x ^ K];
	cnt[x]--;
}

int main() {
	scanf("%d%d%d", &n, &m, &K);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i] ^= a[i - 1];
	t = sqrt(n);
	for (int i = 1; i <= n; i++) pos[i] = i / t;
	for (int i = 1; i <= m; i++)
		scanf("%d%d", &q[i].l, &q[i].r), --q[i].l, q[i].id = i;
	sort(q + 1, q + 1 + m);
	int l = q[1].l, r = q[1].r;
	for (int i = l; i <= r; i++) add(a[i]);
	ans[q[1].id] = res;
	for (int i = 1; i <= m; i++) {
		while (l < q[i].l) del(a[l++]);
		while (l > q[i].l) add(a[--l]);
		while (r < q[i].r) add(a[++r]);
		while (r > q[i].r) del(a[r--]);
		ans[q[i].id] = res;
	}
	for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
	return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 0ms

memory: 5908kb

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: 1ms

memory: 3868kb

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: 1ms

memory: 5908kb

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: 40ms

memory: 6468kb

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: 43ms

memory: 6992kb

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: 43ms

memory: 7036kb

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: 41ms

memory: 6980kb

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: 49ms

memory: 6960kb

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: 49ms

memory: 6468kb

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: 45ms

memory: 6648kb

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