Submission #1314678

#TimeUsernameProblemLanguageResultExecution timeMemory
1314678michael12XOR (IZhO12_xor)C++20
0 / 100
0 ms332 KiB
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
// #define int long long
using namespace std;
const int maxn = 2e5 + 3;
int a[maxn];
pair<int, pair<int, int>> solve(int l, int r){
    if(l == r) return {a[l], {l, r}};
    int mid = (l + r) / 2;
    pair<int, pair<int,int>> left = solve(l, mid);
    pair<int, pair<int, int>> right = solve(mid + 1, r);
    int i = mid;
    int j = mid + 1;
    int cur = a[i] ^ a[j];
    int ans = a[i] ^ a[j];
    int M = i, K = j;
    while(true){
        if(i == l && j == r) break;
        if(l == i && j < r){
            cur = cur ^ a[j + 1];
            j++;
            if(cur > ans){
                K++;
                ans = cur;
            }
        }
        else if(j == r && l < i){
            cur = a[i - 1] ^ cur;
            i--;
            if(cur > ans){
                M--;
                ans = cur;
            }
        }
        else{
            if(a[i - 1] ^ cur >= cur ^ a[j + 1]){
              cur = a[i - 1] ^ cur;
              if(cur > ans){
                 M--;
                 ans = cur;
              }
              i--;

            }
            else{
                cur = cur ^ a[j + 1];
                j++;
                if(cur > ans){
                    K++;
                    ans = cur;
                }
            }
        }
        ans = max(ans, cur);

    } 
    if(ans >= left.ff && ans >= right.ff){
       return {ans, {M, K}};
    }
    else if(left.ff >= right.ff){
        return {left.ff, {left.ss.ff, left.ss.ss}};
    }
    else{
       return {right.ff, {right.ss.ff, right.ss.ss}};
    }
}
signed main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    pair<int, pair<int, int>> T = solve(0, n - 1);
    cout << T.ss.ff + 1<< " " << T.ss.ss + 1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...