Cod sursa(job #2740274)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 12 aprilie 2021 13:03:59
Problema Xor Max Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,s[100005],ans,l,r;
const int inf=1e9;
int arb[5000006];
void update(int nod,int st, int dr, int poz, int val)
{
    if(st==poz&&dr==poz)
    {
        arb[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(nod*2,st,mij,poz,val);
    if(poz>mij)
        update(nod*2+1,mij+1,dr,poz,val);
    arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
int query(int nod,int st,int dr,int a, int b)
{
    if(st>=a&&dr<=b)
        return arb[nod];
    int ans=-1;
    int mij=(st+dr)/2;
    if(a<=mij)
        ans=max(ans,query(nod*2,st,mij,a,b));
    if(b>mij)
        ans=max(ans,query(nod*2+1,mij+1,dr,a,b));
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        fin>>x;
        s[i]=(s[i-1]^x);
    }
    memset(arb,-1,sizeof(arb));
    update(1,0,(1<<21),0,0);
    //fout<<query(1,0,(1<<21),3,120)<<'\n';
    for(int i=1;i<=n;i++)
    {
        bool ok=0;
        if(i==n)
            ok=1;
        int nr=0;
        for(int bit=20;bit>=0;bit--)
        {
            if((s[i]>>bit)&1)
            {
                int st=nr;
                int dr=nr+(1<<bit)-1;
                int bestpoz=query(1,0,(1<<21),st,dr);
                if(bestpoz!=-1)
                {
                    int val=(s[i]^s[bestpoz]);
                    if(val>ans)
                    {
                        ans=val;
                        l=bestpoz+1;
                        r=i;
                    }
                }
                else
                    nr+=(1<<bit);
            }
            else
            {
                int st=nr+(1<<bit);
                int dr=nr+(1<<(bit+1))-1;
                int bestpoz=query(1,0,(1<<21),st,dr);
                if(bestpoz!=-1)
                {
                    int val=(s[i]^s[bestpoz]);
                    if(val>ans)
                    {
                        ans=val;
                        l=bestpoz+1;
                        r=i;
                    }
                    nr+=(1<<bit);
                }
            }
        }
        update(1,0,(1<<21),s[i],i);
    }
    fout<<ans<<" "<<l<<" "<<r;
    return 0;
}