Submission #1136555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136555		imarn	XOR (IZhO12_xor)	C++20	100 / 100	158 ms	7328 KiB

xor

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=3e5+5,inf=1e9+7;
ll a[mxn]{0};
vector<ll>v;
int t[2*mxn];
void upd(int i,int sz,int amt){
    i+=sz;t[i]=min(amt,t[i]);
    for(i>>=1;i;i>>=1)t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int l,int r,int sz,int rs=1e9){
    for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
        if(l&1)rs=min(rs,t[l++]);
        if(r&1)rs=min(rs,t[--r]);
    }return rs;
}int ans[mxn]{0};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,x;cin>>n>>x;
    for(int i=n;i>=1;i--)cin>>a[i];v.pb(0);
    for(int i=1;i<=n;i++)a[i]^=a[i-1],v.pb(a[i]);
    sort(all(v));v.erase(unique(all(v)),v.end());
    int m=v.size();for(int i=0;i<2*m;i++)t[i]=1e9;
    upd(lb(v,0),m,1);
    for(int i=1;i<=n;i++){
        ll cr=0;ans[i]=1e9;
        for(int j=30;j>=0;j--){
            ll xx=((x>>j)&1);
            ll yy=((a[i]>>j)&1);
            if(xx)cr+=(yy^1)*(1<<j);
            else ans[i]=min(ans[i],qr(lb(v,cr+(yy^1)*(1<<j)),ub(v,cr+(yy^1)*(1<<j)+(1<<j)-1),m));
        }ans[i]=min(ans[i],qr(lb(v,cr),ub(v,cr),m));
        upd(lb(v,a[i]),m,i+1);
    }int mx=0,mem=0;
    for(int i=1;i<=n;i++){
        if(ans[i]==1e9)continue;
        if(i-ans[i]+1>=mx){
            mx=i-ans[i]+1;
            mem=i;
        }
    }cout<<n-mem+1<<' '<<mx;
}

• Subtask 1: 100 / 100