bdfz_2024_summer/day5/perfect/fix.cpp.old

63 lines
1.5 KiB
C++

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5+5;
const int MAX_K = 19;
int sMin[MAX_N][MAX_K];
int sMax[MAX_N][MAX_K];
int l2[MAX_N];
#ifndef OITEST
#define PRINT_VALUE(v)
#endif
int main(int argc,char* argv[]){
#ifdef OITEST
// #define PRINT_VALUE(v){cout<<#v<<" :"<<(v)<<endl;}
// PRINT_VALUE(argv[0])
string fileName="perfect";
assert(argc==2);
string num(argv[1]);
string inputFileName = fileName+num+".in";
string ansFileName = fileName+num+".ans";
auto ansFile = ifstream(ansFileName);
auto inputFile =ifstream(inputFileName);
int correctAns;
ansFile>>correctAns;
#define cin inputFile
#endif
cin.sync_with_stdio(false);
cin.tie(0);
l2[0]=0;
l2[1]=0;
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>sMin[i][0];
sMax[i][0]=sMin[i][0];
}
for(int i=2;i<=n;i++){
l2[i]=l2[i/2]+1;
}
int k=l2[n]+1;
for(int j=1;j<=k;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
sMax[i][j]=max(sMax[i][j-1],sMax[i+(1<<(j-1))][j-1]);
sMin[i][j]=min(sMin[i][j-1],sMin[i+(1<<(j-1))][j-1]);
}
}
int ans=INT_MIN;
for(int l=1;l<=n;l++){
for(int r=l;r<=n;r++){
int j=l2[r-l+1];
int maxlr=max(sMax[l][j],sMax[r-(1<<j)+1][j]);
int minlr=min(sMin[l][j],sMin[r-(1<<j)+1][j]);
ans=max(ans,maxlr^minlr);
}
}
cout<<ans<<endl;
#ifdef OITEST
assert(ans==correctAns);
#endif
}