Submission #3149782
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FF first
#define SS second
#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
for(auto& x: xs)
is >> x;
return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
for(unsigned int i=0;i<xs.size();++i)
os << (i?" ":"") << xs[i];
return os;
}
template<class T>
void maxi(T& x, T y){
if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
if(x > y) x = y;
}
const double EPS = 1e-10;
const double PI = acos(-1.0);
const LL MOD = 1e9+7;
constexpr int BLOCK = 4;
__attribute__((aligned(16)))
int as[100010];
__attribute__((aligned(16)))
int lacc[100010];
__attribute__((aligned(16)))
int racc[100010];
__attribute__((aligned(16)))
int lacc_b[100010/BLOCK];
inline int iceil(int a, int b){
return (a + b - 1) / b;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
REP(i,N) cin >> as[i];
for(int i=0;i+BLOCK<=N;i+=BLOCK){
lacc[i] = as[i];
FOR(j,1,BLOCK)
lacc[i+j] = lacc[i+j-1] & as[i+j];
lacc_b[i/BLOCK] = lacc[i+BLOCK-1];
}
racc[0] = as[0];
FOR(i,1,N)
racc[i] = racc[i-1] ^ as[i];
int ans;
int l, r;
cin >> l >> r;
--l;
REP(q,Q){
// solve ans(0-index)
ans = 1<<31;
int a = ~0;
const int bb = l/BLOCK;
const int be = (r-1)/BLOCK;
const int R = racc[r-1];
//FOR(i,l,r) cout<<as[i]<<","; cout<<endl;
if(bb == be){
for(int i=l;i<r-1;++i){
a &= as[i];
maxi(ans, a - (R ^ racc[i]));
}
}
else{
FOR(i,l,(bb+1)*BLOCK){
a &= as[i];
maxi(ans, a - (R ^ racc[i]));
//cout<<i<<","<<a<<"-"<<(R ^ racc[i])<<":"<<ans<<endl;
}
for(int b=bb+1;b<be;++b){
for(int d=0;d<BLOCK;++d){
const int ix = b * BLOCK + d;
int a_ = a & lacc[ix];
int x_ = R ^ racc[ix];
maxi(ans, a_ - x_);
//cout<<ix<<","<<a_<<"-"<<x_<<":"<<ans<<endl;
}
a &= lacc_b[b];
}
for(int i=be*BLOCK;i<r-1;++i){
a &= as[i];
maxi(ans, a - (R ^ racc[i]));
}
}
cout << ans << endl;
ans = abs(ans);
if(q < Q-1){
cin >> l >> r;
l = (l + ans) % N + 1;
r = (r + ans) % N + 1;
--l;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
J - XORAND |
User |
okaduki |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3143 Byte |
Status |
RE |
Exec Time |
4203 ms |
Memory |
2176 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_02.txt |
All |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_pow2_01_mini.txt, subtask1_pow2_02_mini.txt, subtask1_pow2_03_OnlyOneLargeSeg.txt, subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt, subtask1_pow2_05_UniqueLargeSegs.txt, subtask1_pow2_06_randomSegs.txt, subtask1_pow2_07_randomSegs.txt, subtask1_pow2_08_randomSegs.txt, subtask1_pow2_09_x_to_N-x_SegsOnly.txt, subtask1_pow2_10_x_to_N_SegsOnly.txt, subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt, subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt, subtask1_random_01.txt, subtask1_random_02.txt, subtask1_result_minmax_01.txt, subtask1_result_minmax_02.txt, subtask1_result_minmax_03.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample_01.txt |
AC |
1 ms |
256 KB |
subtask0_sample_02.txt |
AC |
1 ms |
256 KB |
subtask1_pow2_01_mini.txt |
AC |
4 ms |
256 KB |
subtask1_pow2_02_mini.txt |
AC |
4 ms |
256 KB |
subtask1_pow2_03_OnlyOneLargeSeg.txt |
RE |
350 ms |
1536 KB |
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt |
TLE |
4203 ms |
1792 KB |
subtask1_pow2_05_UniqueLargeSegs.txt |
RE |
108 ms |
1536 KB |
subtask1_pow2_06_randomSegs.txt |
RE |
107 ms |
1536 KB |
subtask1_pow2_07_randomSegs.txt |
RE |
107 ms |
1536 KB |
subtask1_pow2_08_randomSegs.txt |
RE |
108 ms |
1536 KB |
subtask1_pow2_09_x_to_N-x_SegsOnly.txt |
RE |
108 ms |
1536 KB |
subtask1_pow2_10_x_to_N_SegsOnly.txt |
TLE |
4203 ms |
2176 KB |
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt |
TLE |
4203 ms |
2176 KB |
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt |
TLE |
4203 ms |
1792 KB |
subtask1_random_01.txt |
TLE |
4203 ms |
1664 KB |
subtask1_random_02.txt |
TLE |
4203 ms |
1792 KB |
subtask1_result_minmax_01.txt |
AC |
1 ms |
256 KB |
subtask1_result_minmax_02.txt |
AC |
1 ms |
256 KB |
subtask1_result_minmax_03.txt |
AC |
1 ms |
256 KB |