Cod sursa(job #3353970)

Utilizator mrvalentynTime Limit Exceeded mrvalentyn Data 13 mai 2026 00:14:28
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.03 kb
/*  
    * author: qvalentin  
    * https://codeforces.com/profile/qvalentin
    * 
    * It's you, it'll always be you *
    
*/

#include <bits/stdc++.h>  
using namespace std;  
#define ull unsigned long long  
#define ll long long  
#define pb push_back  
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); 
const int MOD = 1e9+7;
int di[4]={0,0,-1,1};  
int dj[4]={-1,1,0,0};  
      
string FILENAME="xormax";  
ifstream f(FILENAME+".in");  
ofstream g(FILENAME+".out");  


struct Node {
        Node* children[2];
        int end;

        Node() {
                for(int i = 0; i < 2; ++i) {
                        children[i] = nullptr;
                }
                end = 0;
                
        }
};


class Trie {
private:
        Node* root;

        

public:
        Trie(){
                root = new Node();
        }

        void insert(int x, int idx) {
                Node* curr = root;
                
                for(int i = 21; i >= 0; --i) {
                        int bit = (x >> i) & 1;
                        if(!curr->children[bit])curr->children[bit] = new Node();
                        curr = curr->children[bit];
                }
                curr->end = idx;
        }

        pair<int,int> getMax(int x) {
                Node* curr = root;
                int best= 0;
                for(int i = 21; i >= 0; --i) {
                        int bit = (x >> i) & 1;

                        if(curr->children[1-bit]) {
                                best |= (1 << i);
                                curr=curr->children[1-bit];
                        }
                        else {
                                curr=curr->children[bit];
                        }
                }
                return {best, curr->end + 1};
        }

        
};


signed main(){  
        fastio

        //P0 = 0
        //Pi = Pi-1 ^ xi
        //Pi ^ Pj max

        #ifndef qv
        #define cin f
        #define cout g
        #endif

        Trie tr;
        tr.insert(0,0); 


        int n;
        cin>>n;

        int currP = 0;
        int mx = 0;
        int st=1,dr=1;
        int lmn = -1;
        for(int i=1;i<=n;++i) {
                int x;
                cin>>x;
                currP ^= x;
                tr.insert(currP,i);
                
                pair<int,int> tmp = tr.getMax(currP);

                if(tmp.first > mx) {
                        mx = tmp.first;
                        dr = i;
                        st = tmp.second;
                        lmn = dr-st+1;
                }
                else if(tmp.first == mx) {
                        if(i < dr) {
                                dr = i;
                                lmn=dr-st+1;
                        }
                        else if(i == dr) {
                                if(lmn > dr-st+1){
                                        lmn=dr-st+1;
                                }
                        }
                }

        }
        cout<<mx<<' '<<st<<' '<<dr;

        
        return 0;

}