| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #31276 | #1162. 异或 | Wrong Answer | 10 | 8088 ms | 40264 K | C++ 11 / 2.7 K | q3540555 | 2020-07-04 10:10:43 |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 4e5, mxm = 4e5;
struct sgt {
int n;
ll *dta;
void set(int sz) {
n = sz;
dta = new ll[4 * n];
}
void marge(int id) {
int kid[2] = { id * 2, id * 2 + 1 };
dta[id] = dta[kid[0]] ^ dta[kid[1]];
}
void build(ll a[], int l = 0, int r = -1, int id = 1);
ll find(int l, int r, int gl = 0, int gr = -1, int id = 1);
void add(int loc, ll val, int l = 0, int r = -1, int id = 1);
} tr;
void sgt::build(ll a[], int l, int r, int id) {
r = r < 0 ? n : r;
if (l + 1 == r)
return dta[id] = 0, void();
int mid = l + r >> 1;
int kid[2] = { id * 2, id * 2 + 1 };
build(a, l, mid, kid[0]);
build(a, mid, r, kid[1]);
marge(id);
}
ll sgt::find(int l, int r, int gl, int gr, int id) {
gr = gr < 0 ? n : gr;
if (l == gl && r == gr)
return dta[id];
if (l >= r)
return 0;
int mid = gl + gr >> 1;
int kid[2] = { id * 2, id * 2 + 1 };
return find(l, mid, gl, mid, kid[0]) ^ find(mid, r, mid, gr, kid[1]);
}
void sgt::add(int loc, ll val, int l, int r, int id) {
r = r < 0 ? n : r;
if (l > loc || r <= loc)
return;
if (l + 1 == r)
return dta[id] ^= val, void();
int mid = l + r >> 1;
int kid[2] = { id * 2, id * 2 + 1 };
add(loc, val, l, mid, kid[0]);
add(loc, val, mid, r, kid[1]);
marge(id);
}
struct presum {
ll dta[mxn];
ll &operator[](int loc) { return dta[loc]; }
ll get(int l, int r) { return dta[r] ^ dta[l]; }
} chi, tot;
map<ll, int> cnt, pre;
int nxt[mxn], ans[mxm];
vector<pair<int, int>> que[mxn];
ll a[mxn];
int main() {
int n, q;
cin >> n;
tr.set(n);
for (int i = 0; i < n; ++i) cin >> a[i];
// tr.build(a);
for (int i = 0; i < n; ++i) {
chi[i + 1] = chi[i] ^ a[i];
if (cnt[a[i]])
tot[i + 1] = tot[i], nxt[pre[a[i]]] = i;
else
tot[i + 1] = tot[i] ^ a[i];
pre[a[i]] = i;
++cnt[a[i]];
}
cin >> q;
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l;
que[l].push_back({ r, i });
}
for (int i = 0; i < n; ++i) {
for (pair<int, int> aq : que[i]) {
int l = i, r = aq.first, qi = aq.second;
ans[qi] = tot.get(l, r) ^ tr.find(l, r) ^ chi.get(l, r);
}
if (nxt[i])
tr.add(nxt[i], a[i]);
}
for (int i = 0; i < q; ++i) cout << ans[i] << endl;
return 0;
}251838
100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2
<6166055 bytes omitted>0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<852089 bytes omitted>用户输出
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<567998 bytes omitted>系统信息
Exited with return code 0256041
100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2
<5984493 bytes omitted>0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<804650 bytes omitted>用户输出
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<536372 bytes omitted>系统信息
Exited with return code 0907
56 71 13 4 45 57 55 89 12 58 95 99 45 100 42 94 89 94 16 18 55 67 5 68 20 43 51 93 84 92 77 63
<10826 bytes omitted>113
37
35
10
30
69
105
16
64
123
87
73
4
0
91
1
90
94
2
77
118
12
16
48
123
<3772 bytes omitted>用户输出
29
22
22
84
44
100
40
82
63
116
103
94
29
70
54
17
66
40
9
64
114
63
26
82
54
18
27
43
120
82
58
65
19
55
77
100
90
74
103
97
16
<2840 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0911
79 65 67 71 96 98 41 89 63 100 54 9 66 92 97 89 64 44 2 38 94 94 37 91 17 26 38 13 87 96 5 75 1
<10954 bytes omitted>5
68
32
111
15
52
104
119
29
42
98
104
33
104
23
13
57
16
41
81
5
109
53
6
7
<3840 bytes omitted>用户输出
47
83
26
113
101
38
77
93
26
77
101
80
86
84
35
107
46
116
84
84
48
96
84
57
47
46
90
110
16
89
98
77
60
77
26
100
126
27
93
49
<2865 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0910
96 10 58 93 18 79 68 66 20 19 79 50 22 92 79 6 85 16 57 4 81 43 21 39 74 59 34 84 86 39 24 2 6
<10840 bytes omitted>105
19
114
5
48
41
33
108
26
10
108
49
87
48
68
38
110
68
52
4
14
13
120
118
<3759 bytes omitted>用户输出
2
92
71
126
123
73
24
35
92
108
108
10
4
44
117
92
23
8
57
91
93
116
125
89
51
114
108
67
77
4
4
90
113
0
29
110
55
118
9
85
48
<2853 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0908
82 94 2 44 73 45 58 30 18 39 80 54 88 81 37 7 99 59 65 93 22 20 35 57 60 37 46 20 59 88 99 41 3
<11278 bytes omitted>0
60
0
91
79
122
121
78
115
41
103
2
31
59
96
114
23
98
62
45
50
62
122
78
9
<3988 bytes omitted>用户输出
111
13
91
31
70
11
90
56
110
85
54
2
47
59
106
11
19
89
2
20
72
62
17
23
38
22
54
5
31
118
86
77
54
33
69
13
21
73
4
85
108
11
8
<2990 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0978
41 67 43 65 96 23 3 53 34 78 87 67 31 52 74 3 16 45 10 85 96 46 36 0 41 26 85 62 29 0 98 91 47
<10961 bytes omitted>17
80
84
85
54
79
62
124
53
92
84
70
82
98
69
19
39
94
39
117
34
121
89
79
5
<3753 bytes omitted>用户输出
65
43
105
41
28
39
79
98
94
45
120
92
34
10
5
12
20
54
21
21
88
111
71
69
84
80
59
37
75
40
121
50
106
113
110
85
109
56
64
23
5
<2811 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0962
299718210 299718210 0 39962428 59943642 559473992 219793354 939117058 159849712 999060700 97907
<17226 bytes omitted>746812074
909717596
495511252
55402154
812639012
0
919969834
79389020
742767238
787403722
<9685 bytes omitted>用户输出
336443456
503843446
693690536
55402154
874665644
675437892
547432086
614002076
386549778
879295656
306301588
850217486
898927828
<8885 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0935
899154630 939117058 939117058 319699424 319699424 639398848 419605494 659380062 279736996 73930
<17186 bytes omitted>934921578
489567608
451179490
711757202
879173416
69610634
818405958
154782278
137133528
31
<9859 bytes omitted>用户输出
288350384
661478322
647032538
857856680
429542358
485341392
10566278
91898170
1027529198
533956180
839608424
954906656
577614096
<9050 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0935
379643066 0 699342490 219793354 79924856 299718210 219793354 179830926 99906070 79924856 539492
<17019 bytes omitted>352765180
138762976
649995032
331699740
1003139736
28540058
272635836
693480286
952284874
4
<9684 bytes omitted>用户输出
365494228
954127074
434397186
1046555510
1003139736
92101974
1000190064
987469986
648833548
739991800
900082354
683556060
528036
<8935 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0952
599436420 19981214 839210988 899154630 859192202 0 99906070 179830926 539492778 359661852 21979
<17213 bytes omitted>103578644
618951634
383099418
248973264
889950206
51673546
58135816
239774568
597982474
168
<9751 bytes omitted>用户输出
1039057134
489389364
354823134
291501820
147729868
565939146
896830292
426596942
992713702
978088040
916981706
681169766
9927137
<8884 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0962
59943642 239774568 159849712 379643066 119887284 239774568 559473992 379643066 19981214 6393988
<17270 bytes omitted>816843836
2171850
710812428
500992326
93317780
619242180
742511584
592153734
211465332
1070
<9659 bytes omitted>用户输出
809440546
233487820
976744494
947910156
55272244
843581054
1008878160
118187044
295328142
949254382
922743804
165849054
29689820
<8910 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0293327
0 1 0 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0
<4452780 bytes omitted>1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
1
0
<814433 bytes omitted>用户输出
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
0
0
0
1
1
1
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
1
1
1
1
0
1
<542894 bytes omitted>Special Judge 信息
Diff encountered TimeLimitExceeded系统信息
Exited with return code 0268065
0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0
<4495021 bytes omitted>1
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
1
0
0
0
1
0
1
1
1
0
<838052 bytes omitted>用户输出
0
0
1
1
1
0
0
1
1
1
1
1
0
1
1
1
0
0
1
0
1
1
0
1
1
1
1
1
0
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
1
1
0
1
0
0
1
0
0
0
1
0
0
1
0
1
1
<558640 bytes omitted>Special Judge 信息
Diff encountered TimeLimitExceeded系统信息
Exited with return code 0273128
1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0
<4438785 bytes omitted>0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
1
1
1
1
1
0
0
0
1
0
<822920 bytes omitted>用户输出
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
0
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
<548552 bytes omitted>Special Judge 信息
Diff encountered TimeLimitExceeded系统信息
Exited with return code 0256076
0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1
<4077145 bytes omitted>1
1
1
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
1
1
0
0
0
1
1
0
1
0
1
1
1
1
1
<756695 bytes omitted>用户输出
1
1
0
1
1
1
1
0
1
0
1
1
0
1
1
0
0
0
1
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
0
0
1
1
0
1
1
1
0
0
0
1
1
1
0
0
0
0
<504402 bytes omitted>Special Judge 信息
Diff encountered TimeLimitExceeded系统信息
Exited with return code 0286020
1714284 1926072 1256742 1856142 2173824 271728 2259738 1616382 1978020 2221776 1566432 13826
<6399775 bytes omitted>3913446
3562702
1973544
520860
1866136
337592
978922
1314168
3757208
2380906
1135324
3703
<2605049 bytes omitted>用户输出
70332
1854848
3209314
1650234
3481698
4022388
3446620
3125976
1801138
3937432
266256
3338258
2838620
51624
381786
3475710
174501
<2307226 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0293085
1580418 1902096 733266 903096 2211786 699300 763236 721278 2229768 1146852 2149848 2259738 4
<6230057 bytes omitted>3945724
4091218
2106936
3698428
65340
642284
3473038
1346446
3241504
4085906
2386892
3958
<2465891 bytes omitted>用户输出
110354
1509744
341704
1167978
736726
1915096
975098
2742620
2144688
1021450
1146832
2713212
2762580
514428
3043914
1725044
15352
<2184101 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0289253
2293704 1626372 2283714 1954044 1040958 1056942 2289708 303696 1440558 1228770 2063934 90709
<5964250 bytes omitted>2678284
1217318
1450570
3253324
753876
1842350
1581642
4140122
4050490
1114512
3836554
23
<2321125 bytes omitted>用户输出
760072
2428586
3228482
2429864
2087882
233360
202958
1394040
199870
4193772
2923846
1051210
48928
3031896
236792
560554
3680156
<2055637 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0255064
1146852 2093904 1342656 2029968 791208 1110888 1800198 331668 2021976 1730268 1542456 119280
<6096895 bytes omitted>239536
4038706
793690
1566870
4190844
3042696
3755022
469656
3713758
2273578
1261770
3776
<2579881 bytes omitted>用户输出
380612
2207630
767418
194330
696960
972626
2374424
975380
283120
2243574
1907406
2048246
2047708
1181070
3294944
504890
267692
4
<2284777 bytes omitted>Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0