#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #else
// #define dbg(...)
// #endif
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb(n) push_back(n)
#define F first
#define S second
#define mp(x, y) make_pair(x, y)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define nop cout << -1 << endl;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
const ll sup = 1e18;
const ll inf = -1e18;
const ll mod = 1e9 + 7;
const int N_Max = 3e5 + 7;
const int Nax = 15;
const int LOG = 18;
const int BITS = 30;
const int ALPHA = 26;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}
int nxt[30 * N_Max][2], mn[30 * N_Max][2];
int a[N_Max], pref[N_Max];
int N, x, cnt = 1;
int nxt_node(){
return ++cnt;
}
void ins(int val, int ind){
int curr = 1;
for (int i = 30; i >= 0; i--){
int c = (val >> i) & 1;
if (nxt[curr][c] == -1){
mn[curr][c] = ind;
nxt[curr][c] = nxt_node();
}
mn[curr][c] = min(mn[curr][c], ind);
curr = nxt[curr][c];
}
}
int query(int val){
int ret = 2e9, curr = 1;
for (int i = 30; i >= 0; i--){
if (curr == -1) break;
int c = (val >> i) & 1, v = (x >> i) & 1;
if (!v && nxt[curr][c ^ 1] != -1)
ret = min(ret, mn[curr][c ^ 1]);
if (v) curr = nxt[curr][c ^ 1];
else curr = nxt[curr][c];
}
return ret;
}
void solve(){
cin >> N >> x;
memset(nxt, -1, sizeof(nxt));
for (int i = 1; i <= N; i++) cin >> a[i];
for (int i = 1; i <= N; i++) pref[i] = pref[i - 1] ^ a[i];
pair<int, int> ans = {0, 0};
for (int r = 1; r <= N; r++){
ins(pref[r - 1], r);
int l = query(pref[r]);
if (l == 2e9) continue;
if (r - l + 1 > ans.S) ans = {l, r - l + 1};
else if (r - l + 1 == ans.S) ans.F = min(ans.F, l);
}
cout << ans.F << " " << ans.S << endl;
}
int main(){
FAST
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
75612 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
75780 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
