#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 250007, k0 = 30;
int n, k, a[n0], T[2][n0 * k0], sz;
int mn[n0 * k0];
void add(int pos) {
int v = 0, x = a[pos];
for (int i = k0 - 1; i >= 0; i--) {
if (!T[x >> i & 1][v])
T[x >> i & 1][v] = ++sz;
v = T[x >> i & 1][v];
}
mn[v] = min(mn[v], pos);
}
void dfs(int v) {
for (int i = 0; i < 2; i++) {
int to = T[i][v];
if (to) {
dfs(to);
mn[v] = min(mn[v], mn[to]);
}
}
}
int X;
int get(int v, int cur, int x, int d) {
if ((cur ^ x) >= k) return mn[v];
if ((cur ^ x) + (1 << (d + 1)) - 1 < k) return n0;
int res = n0;
for (int i = 0; i < 2; i++) {
int to = T[i][v];
int bit = (i) ? (1 << d) : 0;
int bit2 = X & (1 << d);
if (to) res = min(res, get(to, cur ^ bit, x ^ bit2, d - 1));
}
return res;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
memset(& mn, 0x3f, sizeof(mn));
cin >> n >> k;
add(0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] ^= a[i - 1];
add(i);
}
dfs(0);
int res = 0, ind = -1;
for (int i = 1; i <= n; i++) {
X = a[i];
int l = get(0, 0, 0, k0 - 1);
if (l < i && i - l > res)
res = i - l, ind = i;
}
cout << ind - res + 1 << ' ' << res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
29696 KB |
Output is correct |
2 |
Correct |
15 ms |
29696 KB |
Output is correct |
3 |
Correct |
15 ms |
29696 KB |
Output is correct |
4 |
Correct |
17 ms |
29824 KB |
Output is correct |
5 |
Correct |
23 ms |
30208 KB |
Output is correct |
6 |
Correct |
25 ms |
30336 KB |
Output is correct |
7 |
Correct |
28 ms |
30336 KB |
Output is correct |
8 |
Correct |
27 ms |
30416 KB |
Output is correct |
9 |
Correct |
85 ms |
37496 KB |
Output is correct |
10 |
Correct |
88 ms |
37496 KB |
Output is correct |
11 |
Correct |
77 ms |
37624 KB |
Output is correct |
12 |
Correct |
114 ms |
37496 KB |
Output is correct |
13 |
Correct |
89 ms |
37496 KB |
Output is correct |
14 |
Correct |
87 ms |
37496 KB |
Output is correct |
15 |
Correct |
90 ms |
37524 KB |
Output is correct |
16 |
Correct |
78 ms |
37496 KB |
Output is correct |
17 |
Correct |
212 ms |
46712 KB |
Output is correct |
18 |
Correct |
206 ms |
46760 KB |
Output is correct |
19 |
Correct |
216 ms |
46712 KB |
Output is correct |
20 |
Correct |
228 ms |
46712 KB |
Output is correct |