Submission #1256561

#TimeUsernameProblemLanguageResultExecution timeMemory
1256561lechugonXOR (IZhO12_xor)C++20
100 / 100
95 ms71752 KiB
#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define rep(i,a,b) for(int i = (a); i < (b); i++)
using namespace ::std;
using ll = long long;
typedef vector<int> vi;

const int N = 2e5 + 10;
const int SZ = N * 30 + 5;
const int LOG = 30;
int trie[SZ][2];
int mxId[SZ];
int ct;
const int INF = 1e9 + 10;
void insert(int num , int id){
    int node = 0;
    for(int i = LOG; i >= 0; i--){
        int val = (num >> i) & 1;
        if(trie[node][val] == -1) trie[node][val] = ++ct;
        node = trie[node][val];
        mxId[node] = min(mxId[node] , id);
    }
}
int query(int num, int k) {
    int node = 0;
    int res = INF;
    for(int i = LOG; i >= 0; i--){
        if(node == -1) break;        
        int num_bit = (num >> i) & 1;
        int k_bit =   (k >> i) & 1;
        if(k_bit == 0){
            int opposite = trie[node][num_bit ^ 1];
            if(opposite != -1)
                res = min(res, mxId[opposite]);
            node = trie[node][num_bit];
        }else 
            node = trie[node][num_bit ^ 1];
    }
    if(node != -1)
        res = min(res, mxId[node]);
    return (res == INF) ?  -1 : res;
}
void solve(){
    for(int i = 0; i < SZ; i++) mxId[i] = INF;
    memset(trie, -1 , sizeof trie);
    int n,k; cin >> n >> k;
    vi a(n); for(int i = 0 ; i < n; i++) cin >> a[i];
    int ans = -1;
    int idx = INF;
    int pref = 0;
    for(int i = 0; i < n; i++){
        pref ^= a[i];
        if(pref >= k && i + 1 >= ans) {
            idx = 0;
            ans = i + 1;
            // cout << "Ga: " << idx << '\n';
        }
        else{
            int id = query(pref , k);
            if(id != -1){
                int res = i - id;
                if(res > ans){
                    // cout << "Ans: " << ans << '\n';
                    // cout << "ID: " << id << '\n';
                    // cout << "I: " << i << '\n';
                    ans = max(ans, i - id);
                    idx = id + 1;
                }
            
            }
        }
        insert(pref , i);
    }
    int val = 0;
    for(int i = idx; i <= idx + ans - 1; i++) val ^= a[i];
    assert(val >= k);
    cout << idx + 1 << ' ' << ans << '\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...