Submission #1070907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070907		andrewp	XOR (IZhO12_xor)	C++14	100 / 100	138 ms	92668 KiB

xor

//Dedicated  my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;
#define int ll 

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n'; 

const int N = 250020; 
const int L = 30; 
int n, x, v = 0, a[N], t[N * L][2], val[N * L];
  
void add(int s, int j) {
    int c = 0; 
    for (int i = L - 1; i >= 0; i--) {
        int st = (s >> i) & 1;
        if (t[c][st] == 0) 
            t[c][st] = ++v; 
        c = t[c][st], val[c] = min(val[c], j); 
    }
}

int query(int s) { 
    int ret = n + 1, c = 0, st1, st2;
    for (int i = L - 1; i >= 0; i--) {
        st1 = (s >> i) & 1, st2 = (x >> i) & 1;
        if (st2) {
            if (st1) {
                if (t[c][0] == 0) 
                    break;
                c = t[c][0];
            } else {
                if (t[c][1] == 0) 
                    break;
                c = t[c][1]; 
            }
        } else {
            if (st1) {
                if (t[c][0] != 0) 
                    ret = min(ret, val[t[c][0]]);
                c = t[c][1];
            } else {
                if (t[c][1] != 0)  
                    ret = min(ret, val[t[c][1]]);
                c = t[c][0];
            }
        }
    }
    return ret;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout.tie(nullptr); cerr.tie(nullptr); 

    cin >> n >> x; 
    --x;   
    for (int i = 1; i <= n; i++)  
        cin >> a[i];  
    for (int i = 0; i < N * L; i++) 
        val[i] = n + 1;
    add(0, 0);
    int l = 0, r = 0, ps = 0;
    for (int i = 1; i <= n; i++) {
        ps ^= a[i];
        add(ps, i);
        int upd = query(ps);
        if (i - upd > r) 
            l = upd, r = i - upd;
        else if (upd == r) 
            l = min(l, upd);
    }
    l++;
    cout << l << ' ' << r << '\n'; 
    return 0;   
}

• Subtask 1: 100 / 100