Submission #1336883

#TimeUsernameProblemLanguageResultExecution timeMemory
1336883boclobanchatXOR (IZhO12_xor)C++20
100 / 100
72 ms22412 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int child[MAXN*20][2],V[MAXN*20],A[MAXN],cnode=1;
void ins(int val,int w)
{
	int pos=1;
	V[pos]=max(V[pos],w);
	for(int i=29;i+1;i--)
	{
		int a=(val>>i)%2;
		if(!child[pos][a]) child[pos][a]=++cnode;
		pos=child[pos][a],V[pos]=max(V[pos],w);
	}
}
int get(int val,int x)
{
	if((--x)<0) return V[1];
	int ans=0,pos=1;
	for(int i=29;i+1;i--)
	{
		int a=((val^x)>>i)%2;
		if(!((x>>i)%2)&&child[pos][a^1]) ans=max(ans,V[child[pos][a^1]]);
		if(!child[pos][a]) break;
		pos=child[pos][a];
	}
	return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,x;
    cin>>n>>x;
    int mx=-1,pos=0;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=n;i;i--)
    {
    	A[i]^=A[i+1];
    	ins(A[i+1],i+1);
    	int res=get(A[i],x);
    	if(mx<=res-i) mx=res-i,pos=i;
	}
	cout<<pos<<" "<<mx;
}
#Verdict Execution timeMemoryGrader output
Fetching results...