Submission #528330
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;
struct Trie {
int t;
Trie *n[2];
};
static Trie* insert(Trie *u, int x, int t, int j) {
auto r = new Trie;
r->t = t;
if(u == nullptr) {
r->n[0] = nullptr;
r->n[1] = nullptr;
} else {
r->n[0] = u->n[0];
r->n[1] = u->n[1];
}
if(j > 0) {
auto c = x >> --j & 1;
r->n[c] = insert(r->n[c], x, t, j);
}
return r;
}
static int A[NMAX];
static int X[NMAX + 1];
static int Z[NMAX][B];
static Trie *H[NMAX + 1];
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 qquery(int x, Trie *u, int r) {
auto p = 0;
for(auto j = B; --j >= 0; ) {
auto c = x >> j & 1;
if(u->n[c] == nullptr || u->n[c]->t > r) c ^= 1;
u = u->n[c];
assert(u != nullptr && u->t <= r);
p = p << 1 | c;
}
return p ^ x;
}
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 - qquery(X[r + 1], H[l + 1], z[i]));
//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 j = 0; j < B; j++) Z[N][j] = N;
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];
}
H[i] = insert(H[i + 1], X[i], i, B);
}
int m;
for(auto q = 0; q < Q; q++) {
int l, r;
scanf("%d%d", &l, &r);
if(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 |
100 |
Code Size |
2254 Byte |
Status |
AC |
Exec Time |
1364 ms |
Memory |
114812 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:79: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:80: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:92: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 |
100 / 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 |
29 ms |
972 KB |
subtask0_sample_02.txt |
AC |
28 ms |
1044 KB |
subtask1_pow2_01_mini.txt |
AC |
36 ms |
2120 KB |
subtask1_pow2_02_mini.txt |
AC |
36 ms |
2072 KB |
subtask1_pow2_03_OnlyOneLargeSeg.txt |
AC |
809 ms |
114648 KB |
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt |
AC |
1047 ms |
114636 KB |
subtask1_pow2_05_UniqueLargeSegs.txt |
AC |
690 ms |
114580 KB |
subtask1_pow2_06_randomSegs.txt |
AC |
720 ms |
114648 KB |
subtask1_pow2_07_randomSegs.txt |
AC |
731 ms |
114800 KB |
subtask1_pow2_08_randomSegs.txt |
AC |
754 ms |
114712 KB |
subtask1_pow2_09_x_to_N-x_SegsOnly.txt |
AC |
763 ms |
114812 KB |
subtask1_pow2_10_x_to_N_SegsOnly.txt |
AC |
753 ms |
114584 KB |
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt |
AC |
1364 ms |
114644 KB |
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt |
AC |
1018 ms |
114580 KB |
subtask1_random_01.txt |
AC |
609 ms |
114584 KB |
subtask1_random_02.txt |
AC |
612 ms |
114644 KB |
subtask1_result_minmax_01.txt |
AC |
27 ms |
1172 KB |
subtask1_result_minmax_02.txt |
AC |
29 ms |
1044 KB |
subtask1_result_minmax_03.txt |
AC |
28 ms |
1048 KB |