Submission #1127808


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))
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 main() {
    int n, q; scanf("%d%d", &n, &q);
    repeat (i,n) scanf("%u", &a[i]);
    xor_acc[0] = 0;
    repeat (i,n) xor_acc[i+1] = xor_acc[i] ^ a[i];
    ll m = - inf;
    while (q --) {
        int l, r; scanf("%d%d", &l, &r);
        if (m == - inf) {
            -- l;
        } else {
            l = (l + abs(m)) % n;
            r = (r + abs(m)) % n + 1;
        }
        int32_t x = xor_acc[r] ^ xor_acc[l];
        int32_t d = 0x7fffffff;
        m = - inf;
        int i;
        for (i = l; i < r-1-8; i += 8) {
            x ^= xor_acc[i];
            ll m0 = (d & a[i]                                                               ) -(ll) (x ^ xor_acc[i+1]);
            ll m1 = (d & a[i] & a[i+1]                                                      ) -(ll) (x ^ xor_acc[i+2]);
            ll m2 = (d & a[i] & a[i+1] & a[i+2]                                             ) -(ll) (x ^ xor_acc[i+3]);
            ll m3 = (d & a[i] & a[i+1] & a[i+2] & a[i+3]                                    ) -(ll) (x ^ xor_acc[i+4]);
            ll m4 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4]                           ) -(ll) (x ^ xor_acc[i+5]);
            ll m5 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5]                  ) -(ll) (x ^ xor_acc[i+6]);
            ll m6 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5] & a[i+6]         ) -(ll) (x ^ xor_acc[i+7]);
            ll m7 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5] & a[i+6] & a[i+7]) -(ll) (x ^ xor_acc[i+8]);
            m0 = max(m0, m1);
            m2 = max(m2, m3);
            m4 = max(m4, m5);
            m6 = max(m6, m7);
            m0 = max(m0, m2);
            m4 = max(m4, m6);
            m0 = max(m0, m4);
            m  = max(m,  m0);
            d &= a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5] & a[i+6] & a[i+7];
            x ^= xor_acc[i+8];
        }
        for (; i < r-1; ++ i) {
            d &= a[i];
            x ^= a[i];
            m = max(m, d -(ll) x);
        }
        printf("%lld\n", m);
    }
    return 0;
}

Submission Info

Submission Time
Task J - XORAND
User kimiyuki
Language C++14 (Clang 3.8.0)
Score 0
Code Size 2396 Byte
Status TLE
Exec Time 4203 ms
Memory 2048 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 7
TLE × 12
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 256 KB
subtask1_pow2_02_mini.txt AC 3 ms 256 KB
subtask1_pow2_03_OnlyOneLargeSeg.txt TLE 4203 ms 1408 KB
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt TLE 4203 ms 1408 KB
subtask1_pow2_05_UniqueLargeSegs.txt TLE 4203 ms 1408 KB
subtask1_pow2_06_randomSegs.txt TLE 4203 ms 2048 KB
subtask1_pow2_07_randomSegs.txt TLE 4203 ms 2048 KB
subtask1_pow2_08_randomSegs.txt TLE 4203 ms 2048 KB
subtask1_pow2_09_x_to_N-x_SegsOnly.txt TLE 4203 ms 1664 KB
subtask1_pow2_10_x_to_N_SegsOnly.txt TLE 4203 ms 1664 KB
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt TLE 4203 ms 1664 KB
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt TLE 4203 ms 1280 KB
subtask1_random_01.txt TLE 4203 ms 1280 KB
subtask1_random_02.txt TLE 4203 ms 1280 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