Submission #1005738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005738		12345678	XOR (IZhO12_xor)	C++17	100 / 100	121 ms	60496 KiB

xor

#include <bits/stdc++.h>

using namespace std;

const int nx=250005;


int n, x, a[nx], qs[nx];
pair<int, int> mx;
bitset<31> b;

struct node
{
    int mn;
    node *l, *r;
    node(int mn): mn(mn), l(0), r(0){}
};
typedef node* pnode;
pnode rt=new node(1e9);

void add(pnode &t, int idx, int lvl)
{
    if (!t) t=new node(idx);
    t->mn=min(t->mn, idx);
    if (lvl<0) return;
    if (qs[idx]&(1<<lvl)) add(t->r, idx, lvl-1);
    else add(t->l, idx, lvl-1);
}

int query(pnode t, int vl, int cur, int lvl)
{
    b=cur;
    if (cur>=x) return t->mn;
    if (lvl!=30&&(cur+(1<<(lvl+1))-1)<x) return 1e9;
    int res=1e9;
    if (t->l) res=min(res, query(t->l, vl, cur+((vl&(1<<lvl))), lvl-1));
    if (t->r) res=min(res, query(t->r, vl, cur+(((vl&(1<<lvl))^(1<<lvl))), lvl-1));
    return res;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>x;
    for (int i=1; i<=n; i++) cin>>a[i], qs[i]=a[i]^qs[i-1];
    for (int i=1; i<=n; i++)
    {
        add(rt, i-1, 30);
        int tmp=query(rt, qs[i], 0, 30);
        mx=max(mx, {i-tmp, -tmp-1});
    }
    cout<<-mx.second<<' '<<mx.first;
}

• Subtask 1: 100 / 100