#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 time | Memory | Grader output |
|---|
| Fetching results... |