#include <bits/stdc++.h>
// you just try again
using namespace std;
#define ll long long
void read() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}
const int N = 3e5 + 5;
struct trie {
vector<array<int, 3> > tree; // 0 , 1 , minidx;
int len;
trie() {
len = 0;
tree.push_back({-1, -1, N});
}
void insert(int val, int id) {
int idx = 0;
for (int i = 30; ~i; i--) {
int bit = (val >> i) & 1;
if (tree[idx][bit] == -1) {
tree.push_back({-1, -1, N});
tree[idx][bit] = ++len;
}
idx = tree[idx][bit];
tree[idx][2] = min(tree[idx][2], id);
}
}
int query(int x, int k) {
int idx = 0, ret = N;
for (int i = 30; ~i; --i) {
int bitx = (x >> i) & 1;
int bitk = (k >> i) & 1;
if (!bitk && ~tree[idx][bitx ^ 1])ret = min(ret, tree[tree[idx][bitx ^ 1]][2]);
if (tree[idx][bitk ^ bitx] == -1)break;
idx = tree[idx][bitk ^ bitx];
}
return ret;
}
};
void code() {
int n, k;
cin >> n >> k;
trie tr;
tr.insert(0, 0);
int idx, mx = 0, pre = 0;
for (int i = 1; i <= n; i++) {
int val;
cin >> val;
pre ^= val;
int len = i - tr.query(pre, k - 1);
if (len > mx) {
mx = len;
idx = i;
}
tr.insert(pre,i);
}
cout << idx - mx + 1 << " " << mx;
}
int main() {
read();
int t = 1;
// cin >> t;
while (t--)
code();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |