Pagini recente » Cod sursa (job #2119707) | Monitorul de evaluare | Cod sursa (job #847477) | Cod sursa (job #1337539) | Cod sursa (job #2740290)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
typedef long long ll;
int n,s[200005],l,r;
struct node
{
int bestpoz;
int muchii[2];
};
node emptynode;
vector<node> t;
ll ans;
const int inf=1e9;
void addnum(int nr, int index)
{
int v=0;
for(int bit=20;bit>=0;bit--)
{
int val;
if((nr>>bit)&1)
val=1;
else
val=0;
if(t[v].muchii[val]==-1)
{
node x=emptynode;
x.bestpoz=index;
t[v].muchii[val]=t.size();
t.push_back(x);
}
v=t[v].muchii[val];
t[v].bestpoz=index;
}
}
int go(int nod,int val)
{
return t[nod].muchii[val];
}
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);
}
/*if(n==1)
{
fout<<s[1]<<" 1 1";
return 0;
}*/
//fout<<query(1,0,(1<<21),3,120)<<'\n';
emptynode.muchii[0]=-1;
emptynode.muchii[1]=-1;
t.push_back(emptynode);
addnum(s[0],0);
for(int i=1;i<=n;i++)
{
int nr=0;
int v=0;
for(int bit=20;bit>=0;bit--)
{
if((s[i]>>bit)&1)
{
if(go(v,0)!=-1)
{
int bestpoz=t[go(v,0)].bestpoz;
int val=(s[i]^s[bestpoz]);
if(val>ans)
{
ans=val;
l=bestpoz+1;
r=i;
}
v=go(v,0);
}
else
{
nr+=(1<<bit);
v=go(v,1);
}
}
else
{
if(go(v,1)!=-1)
{
int bestpoz=t[go(v,1)].bestpoz;
int val=(s[i]^s[bestpoz]);
if(val>ans)
{
ans=val;
l=bestpoz+1;
r=i;
}
v=go(v,1);
nr+=(1<<bit);
}
else
v=go(v,0);
}
}
addnum(s[i],i);
}
if(l==0&&r==0)
{
fout<<s[1]<<" "<<1<<" "<<1;
return 0;
}
fout<<ans<<" "<<l<<" "<<r;
return 0;
}