#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
#define int long long
const int maxn = 250069;
int trie[30 * maxn][2], n, a[maxn], id, y;
int c[30 * maxn];
void add(int x, int p) {
int node = 0;
for (int i = 29;i >= 0;i--) {
int k = ((x & (1 << i)) > 0);
if (trie[node][k] == 0)
trie[node][k] = ++id;
node = trie[node][k];
c[node] = min(c[node], p);
}
}
int search(int x) {
int res = n + 1, node = 0;
for (int i = 29;i >= 0;i--) {
int k = ((x & (1 << i)) > 0);
if (y & (1 << i)) {
int dr;
if (k > 0)
dr = 0;
else
dr = 1;
if (!trie[node][dr])
break;
node = trie[node][dr];
}
else {
int dr;
if (k > 0)
dr = 0;
else
dr = 1;
if (trie[node][dr])
res = min(res, c[trie[node][dr]]);
node = trie[node][dr ^ 1];
}
}
return res;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while(tt--) {
cin >> n >> y;
--y;
// treba mi strknto veci od y sad
for (int i = 1;i <= n;i++)
cin >> a[i];
for (int i = 1;i < 30 * maxn;i++)
c[i] = n + 1;
add(0, 0);
int ind = 0, k = 0, xr = 0;
for (int i = 1;i <= n;i++) {
xr ^= a[i];
add(xr, i);
int rez = search(xr);
if (i - rez > k) {
k = i - rez;
ind = rez;
}
else if (rez == k)
ind = min(ind, rez);
}
cout << ind + 1 << " " << k;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
62040 KB |
Output is correct |
2 |
Correct |
8 ms |
62044 KB |
Output is correct |
3 |
Correct |
9 ms |
62152 KB |
Output is correct |
4 |
Correct |
10 ms |
62044 KB |
Output is correct |
5 |
Correct |
12 ms |
62296 KB |
Output is correct |
6 |
Correct |
14 ms |
62300 KB |
Output is correct |
7 |
Correct |
13 ms |
62300 KB |
Output is correct |
8 |
Correct |
15 ms |
62300 KB |
Output is correct |
9 |
Correct |
35 ms |
75092 KB |
Output is correct |
10 |
Correct |
35 ms |
75096 KB |
Output is correct |
11 |
Correct |
38 ms |
74992 KB |
Output is correct |
12 |
Correct |
37 ms |
75092 KB |
Output is correct |
13 |
Correct |
38 ms |
74924 KB |
Output is correct |
14 |
Correct |
36 ms |
75068 KB |
Output is correct |
15 |
Correct |
35 ms |
75212 KB |
Output is correct |
16 |
Correct |
39 ms |
75088 KB |
Output is correct |
17 |
Correct |
106 ms |
91056 KB |
Output is correct |
18 |
Correct |
97 ms |
91148 KB |
Output is correct |
19 |
Correct |
112 ms |
91376 KB |
Output is correct |
20 |
Correct |
104 ms |
90904 KB |
Output is correct |