Submission #1280160

#TimeUsernameProblemLanguageResultExecution timeMemory
1280160_el_patronXOR (IZhO12_xor)C++20
0 / 100
1 ms568 KiB
/**

    (وَأَنْ لَيْسَ لِلْإِنْسَانِ إِلَّا مَا سَعَىٰ * وَأَنَّ سَعْيَهُ سَوْفَ يُرَىٰ)
    (النجم: 39-40)


**/

//      Always keep moving



//#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")


#include<bits/stdc++.h>
#define endl "\n"

using namespace std;
typedef long long ll;
typedef __int128_t Big;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
//#define int long long

#define Fcin ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr);
const ll oo = (ll)1e18+1;
#define eb emplace_back
#define pb push_back
#define in insert
#define fs first
#define sc second
const ll MOD=1e9+7;
#define all(ds) ds.begin(),ds.end()
#define rall(ds) ds.rbegin(),ds.rend()
#define Sort(ds) sort(ds.begin(),ds.end())
#define sortc(ds,co) sort(ds.begin(),ds.end(),co)
#define FastFib(n) round((double)(pow((1+sqrt(5)),n)-pow((1-sqrt(5)),n))/(double)((1<<n)*sqrt(5)))
#define popCnt(x) (__builtin_popcountll(x))
#define show(name) Show(#name,(name))
void Show(char *name,ll value)
{
    cout<<name<<" = "<<value<<endl;
}

/*
struct SegTree{

    #define lf (x * 2 + 1)
    #define rt (x * 2 + 2)
    #define md ((lx+rx)>>1)





    int n;

    vector<array<int,2>> tree;


    SegTree(int m)
    {
        n = m+1;
        tree.assign(n*4,{0,0});
        build(0,n);
    }


    void build(int l,int r ,int x = 0,int lx = 0,int rx = -1)
    {
        if(rx==-1)
            rx = n-1;

        if(lx==rx)
        {
            tree[x] = {0,rx};
            return ;
        }
        build(l,r,lf,lx,md);
        build(l,r,rt,md+1,rx);
        tree[x] = merge(tree[lf],tree[rt]);
    }


    void update(int i,int val,int x = 0,int lx = 0,int rx = -1)
    {
        if(rx==-1)
            rx = n-1;

        if(lx==rx){
            tree[x][0] += val;
            return ;
        }

        if(i<=md)
        update(i,val,lf,lx,md);
        else
        update(i,val,rt,md+1,rx);
        tree[x] = merge(tree[lf] , tree[rt]);
    }


    array<int,2> query(int l,int r,int x = 0,int lx = 0,int rx = -1)
    {
        if(rx==-1)
            rx = n-1;
        if(rx<l or lx>r)return {false,0};
        if(lx>=l and rx<=r)return tree[x];

        return merge(query(l,r,lf,lx,md) , query(l,r,rt,md+1,rx));
    }



    #undef lf
    #undef rt
    #undef md

};

*/


string s;

const int m = 1e9+7;

struct Hash{

    int p , n;

    vector<int> h,pw;

    Hash(int nt,int pt) : n(nt) , p(pt)
    {
        h.resize(n+1);
        pw.resize(n+1);
        init();
        hash_s();

    }

    void hash_s()
    {
        h[0] = 0;
        for(int i=1;i<=s.size();i++)
        {
            h[i] = ((h[i-1]*p)+(s[i-1]-'a'+1))%m;
        }
    }



    int calc(int l,int r)
    {
        return ((h[r]-h[l-1]*pw[r-l+1])%m + m)%m;
    }


    void init()
    {
        pw[0] = 1;
        for(int i=1;i<=n;i++)
            pw[i] = (pw[i-1]*p)%m;
    }

};




struct Hash_sfx{

    int p , n ;

    vector<int> h,pw;

    Hash_sfx(int nt,int pt) : n(nt) , p(pt)
    {
        h.resize(n+2);
        pw.resize(n+2);
        init();
        hash_s();

    }

    void hash_s()
    {
        h.back() = 0;
        for(int i=s.size();i>=1;i--)
        {
            h[i] = ((h[i+1]*p)+(s[i-1]-'a'+1))%m;
        }
    }



    int calc(int l,int r)
    {
        return ((h[l]-h[r+1]*pw[r-l+1])%m + m)%m;
    }


    void init()
    {
        pw[0] = 1;
        for(int i=1;i<=n;i++)
            pw[i] = (pw[i-1]*p)%m;
    }

};



struct node{
    int next[2] = {};
    int cnt,mn;
    node(){cnt = 0;mn = 1e9;}
};



/*
void push(vector<node> &trie,string &s)
{
    int cur = 0;
    for(int i=0;i<s.size();i++)
    {

        if(!trie[cur].next.count(s[i]-'a'))
            trie[cur].next[s[i]-'a'] = trie.size() ,
            trie.emplace_back() , trie[trie.size()-1].ch = s[i];

        cur = trie[cur].next[s[i]-'a'];
        trie[cur].cnt++;
    }
    trie[cur].end_cnt++;
}



int check(vector<node> &trie,string &s){
    int u = 0;
    for(auto c:s)
    {
        if(!trie[u].next[c-'a'])return false;
        u = trie[u].next[c-'a'];
    }
    return true;
}


int search (vector<node> &trie,string &s,int i,int u){
    if(i==s.size() or !trie[u].next.count(s[i]-'a'))return trie[u].cnt;
    return (u?trie[u].cnt:0) + search(trie,s,i+1,trie[u].next[s[i]-'a']);
};
*/


signed main()
{
    Fcin
    ll t,i,a,b,x,m,w,y;
    t=1;
//    cin>>t;

    cout<<fixed<<setprecision(9);

    while(t--)
    {
        int n,q,k;
        cin>>n>>k;
        vector<int> v(n);
        for(auto &n:v)cin>>n;
        int cur = 0;
        vector<node> trie(1);

        auto push = [](vector<node> &trie,int n,int idx)
        {
            int u = 0;
            for(int i=30;i>=0;i--)
            {
                if(!trie[u].next[n>>i&1])
                    trie[u].next[n>>i&1] = trie.size() , trie.emplace_back();
                u = trie[u].next[n>>i&1];
                trie[u].mn = min(trie[u].mn,idx);
                trie[u].cnt++;
            }
        };


        auto solve = [](vector<node> &trie,int n,int k)
        {
            ll u = 0 ;
            int res = 1e9 , i = 32;
            for(i=30;i>=0;i--)
            {
                if((n>>i&1) and (k>>i&1))
                {
                    u = trie[u].next[0];
                }else if((n>>i&1) and !(k>>i&1))
                {
                    res = min(res,trie[trie[u].next[0]].mn);
                    u = trie[u].next[1];
                }else if(!(n>>i&1) and (k>>i&1))
                {
                    u = trie[u].next[1];
                }else {
                    res = min(res,trie[trie[u].next[1]].mn);
                    u = trie[u].next[0];
                }
                if(!u)break;
            }
            return res;
        };


        array<int,2> ans = {-1,-1};

        for(i=0;i<n;i++)
        {
            cur ^= v[i];
            push(trie,cur,i);
            int j = solve(trie,cur,k)+1;
            if(i-j>ans[1]-ans[0])ans = {j,i};
        }
        cout<<ans[0]+1<<" "<<ans[1]-ans[0]+1;
    }
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:335:43: warning: narrowing conversion of 'i' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  335 |             if(i-j>ans[1]-ans[0])ans = {j,i};
      |                                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...