Submission #528292
Source Code Expand
#include <cassert>
#include <climits>
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <algorithm>
template<class T> static inline void MAZ(T &a, T b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, T b) {if(b < a) a = b;}
static const auto NMAX = 100000;
static const auto B = 31;
static int A[NMAX];
static int X[NMAX + 1];
static int Z[NMAX][B];
static int query(int x, int l, int r) {
auto ret = X[l] ^ x;
while(++l <= r) MIZ(ret, X[l] ^ x);
return ret;
}
static int solve(int l, int r) {
auto zn = 0; int z[B + 1];
for(auto j = 0; j < B; j++) {
if(Z[l][j] != l && Z[l][j] < r) z[zn++] = Z[l][j];
}
std::sort(z, z + zn);
zn = std::unique(z, z + zn) - z;
z[zn] = r;
auto ret = INT_MIN, AND = A[l];
for(auto i = 0; ; ) {
MAZ(ret, AND - query(X[r + 1], l + 1, z[i]));
if(i == zn) break;
AND &= A[z[i]];
i++;
}
return ret;
}
int main() {
int N, Q;
scanf("%d%d", &N, &Q);
for(auto i = 0; i < N; i++) scanf("%d", A + i);
for(auto i = N; --i >= 0; ) {
X[i] = A[i] ^ X[i + 1];
for(auto j = 0; j < B; j++) {
Z[i][j] = (A[i] >> j & 1) == 0 ? i : Z[i + 1][j];
}
}
int m;
for(auto q = 0; q < Q; q++) {
int l, r;
scanf("%d%d", &l, &r);
if(true && q != 0) {
l = (l + (int64_t)abs(m)) % N + 1;
r = (r + (int64_t)abs(m)) % N + 1;
}
l--; r--;
assert(0 <= l && l < r && r < N);
m = solve(l, r);
printf("%d\n", m);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
J - XORAND |
User |
arosusti |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
1479 Byte |
Status |
TLE |
Exec Time |
4051 ms |
Memory |
13912 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:43:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
^
./Main.cpp:44:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(auto i = 0; i < N; i++) scanf("%d", A + i);
^
./Main.cpp:54:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &l, &r);
^
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 |
64 ms |
948 KB |
subtask0_sample_02.txt |
AC |
26 ms |
916 KB |
subtask1_pow2_01_mini.txt |
AC |
29 ms |
1048 KB |
subtask1_pow2_02_mini.txt |
AC |
31 ms |
984 KB |
subtask1_pow2_03_OnlyOneLargeSeg.txt |
TLE |
4038 ms |
13848 KB |
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt |
TLE |
4040 ms |
13848 KB |
subtask1_pow2_05_UniqueLargeSegs.txt |
TLE |
4051 ms |
13880 KB |
subtask1_pow2_06_randomSegs.txt |
TLE |
4038 ms |
13912 KB |
subtask1_pow2_07_randomSegs.txt |
TLE |
4038 ms |
13892 KB |
subtask1_pow2_08_randomSegs.txt |
TLE |
4036 ms |
13860 KB |
subtask1_pow2_09_x_to_N-x_SegsOnly.txt |
TLE |
4038 ms |
13908 KB |
subtask1_pow2_10_x_to_N_SegsOnly.txt |
TLE |
4038 ms |
13896 KB |
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt |
TLE |
4038 ms |
13848 KB |
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt |
TLE |
4037 ms |
13840 KB |
subtask1_random_01.txt |
TLE |
4038 ms |
13892 KB |
subtask1_random_02.txt |
TLE |
4038 ms |
13848 KB |
subtask1_result_minmax_01.txt |
AC |
26 ms |
944 KB |
subtask1_result_minmax_02.txt |
AC |
28 ms |
940 KB |
subtask1_result_minmax_03.txt |
AC |
26 ms |
952 KB |