Submission #1127869
Source Code Expand
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
const ll inf = ll(1e18)+9;
#define N_MAX 100000
int32_t a[N_MAX];
int32_t xor_acc[N_MAX+1];
int and_skip[N_MAX][31];
int main() {
// input
int n, q; scanf("%d%d", &n, &q);
repeat (i,n) scanf("%u", &a[i]);
{ // prepare
xor_acc[0] = 0;
repeat (i,n) xor_acc[i+1] = xor_acc[i] ^ a[i];
repeat (k,31) and_skip[n-1][k] = n;
repeat_reverse (i,n-1) {
repeat (k,31) {
and_skip[i][k] = and_skip[i+1][k];
if (not (a[i+1] & (1<<k))) and_skip[i][k] = i+1;
}
}
}
// query
ll m = - inf;
while (q --) {
// input
int l, r; scanf("%d%d", &l, &r);
if (m == - inf) {
-- l;
} else {
l = (l + abs(m)) % n;
r = (r + abs(m)) % n + 1;
}
// solve
m = - inf;
int32_t d = a[l];
for (int i = l; i < r-1; ) {
int ni = r-1;
repeat (k,31) if (d & (1<<k)) ni = min(ni, and_skip[i][k]);
int32_t x = 0x7fffffff;
repeat_from (j,i,ni) {
x = min(x, xor_acc[r] ^ xor_acc[j+1]);
}
m = max(m, d -(ll) x);
d &= a[ni];
i = ni;
}
// output
printf("%lld\n", m);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
J - XORAND |
User |
kimiyuki |
Language |
C++14 (Clang 3.8.0) |
Score |
100 |
Code Size |
1618 Byte |
Status |
AC |
Exec Time |
2456 ms |
Memory |
14208 KB |
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 |
1 ms |
256 KB |
subtask0_sample_02.txt |
AC |
1 ms |
256 KB |
subtask1_pow2_01_mini.txt |
AC |
3 ms |
384 KB |
subtask1_pow2_02_mini.txt |
AC |
3 ms |
384 KB |
subtask1_pow2_03_OnlyOneLargeSeg.txt |
AC |
2401 ms |
14208 KB |
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt |
AC |
2434 ms |
14080 KB |
subtask1_pow2_05_UniqueLargeSegs.txt |
AC |
2303 ms |
14208 KB |
subtask1_pow2_06_randomSegs.txt |
AC |
851 ms |
14080 KB |
subtask1_pow2_07_randomSegs.txt |
AC |
848 ms |
14208 KB |
subtask1_pow2_08_randomSegs.txt |
AC |
860 ms |
14208 KB |
subtask1_pow2_09_x_to_N-x_SegsOnly.txt |
AC |
1237 ms |
14208 KB |
subtask1_pow2_10_x_to_N_SegsOnly.txt |
AC |
1230 ms |
14208 KB |
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt |
AC |
1198 ms |
14080 KB |
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt |
AC |
2456 ms |
13952 KB |
subtask1_random_01.txt |
AC |
797 ms |
13312 KB |
subtask1_random_02.txt |
AC |
793 ms |
13312 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 |