Submission #1266120

#TimeUsernameProblemLanguageResultExecution timeMemory
1266120rayan_bdXOR (IZhO12_xor)C++20
0 / 100
1 ms320 KiB
#include <bits/stdc++.h>
using namespace std;
const int mxN = 950005;
#define int long long
const int INF = 1e18;
int seg[mxN * 4], a[mxN];
void upd(int node, int start, int end, int idx, int v){
    if(start == end){
        seg[node] = v;
        return;
    }
    int mid = start + (end - start) / 2;
    if(idx <= mid){
        upd(node * 2 + 1, start, mid, idx, v);
    }else{
        upd(node * 2 + 2, mid + 1, end, idx, v);
    }
    seg[node] = min(seg[node * 2 + 1], seg[node * 2 + 2]);
}
int query(int node, int start, int end, int l, int r){
    if(start > r || end < l) return INF;
    if(start >= l && end <= r) return seg[node];
    int mid = start + (end - start) / 2;
    return min(query(node * 2 + 1, start, mid, l, r),
               query(node * 2 + 2, mid + 1, end, l, r));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, x, pref = 0;
    cin >> n >> x;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    pair<int, int> ans = {0, 0};
    for(int i = 1; i <= n; ++i){
       upd(0, 1, n, i, pref ^ x);
       pref ^= a[i];
       int st = 1, en = i, best = -1;
       while(st <= en){
        int mid = st + (en - st) / 2;
        if(pref >= query(0, 1, n, 1, mid)){
            best = mid;
            en = mid - 1;
        }else{
            st = mid + 1;
        }
       }
       if(best != -1){
        if((i - best + 1) == ans.first){
            ans = min(ans, {i - best + 1, best});
        }else{
            ans = max(ans, {i - best + 1, best});
        }
       }
       // p[r] >= p[l - 1] ^ x
    }
    cout << ans.second << " " << ans.first << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...