Submission #528210
Source Code Expand
/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
typedef int8_t sbyte;
typedef uint8_t byte;
typedef uint16_t ushort;
typedef uint32_t uint;
typedef int64_t i64;
typedef uint64_t u64;
template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;}
template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;}
/*}}}*/
static const auto NMAX = 100000;
static const auto B = 31;
static int N, Q;
static uint A[NMAX], R[NMAX + 1];
static vector<int> Z[B];
static vector<pair<uint, int>> T;
static uint solve(int r, int ll, int lr) {
auto u = (uint)1;
for(auto j = B; --j >= 0; ) {
u = (u << 1) | (R[r] >> j & 1);
auto it = lower_bound(begin(T), end(T), make_pair(u, ll));
if(it == end(T) || it->first != u || it->second > lr) u ^= 1;
}
return u ^ ((uint)1 << B) ^ R[r];
}
static i64 solve(int l, int r) {
i64 ret = LLONG_MIN;
vector<pair<int, uint>> z;
for(auto j = 0; j < B; j++) {
auto it = lower_bound(begin(Z[j]), end(Z[j]), l);
if(it != Z[j].end() && l < *it && *it < r) {
z.emplace_back(*it, ~((uint)1 << j));
}
}
sort(begin(z), end(z));
auto zn = 0;
for(auto &p : z) {
if(zn != 0 && p.first == z[zn - 1].first) {
z[zn - 1].second &= p.second;
} else {
z[zn++] = p;
}
}
z.resize(zn);
z.emplace_back(r, 0);
i64 b = A[l];
for(auto i = 0, p = l; ; ) {
MAZ(ret, b - solve(r + 1, p + 1, z[i].first));
b &= z[i].second;
p = z[i].first;
if(i++ == zn) break;
}
return ret;
}
static void solve() {
i64 m;
for(auto q = 0; q < Q; q++) {
int l, r;
scanf("%d%d", &l, &r);
if(q != 0) {
l = (l + abs(m)) % N + 1;
r = (r + abs(m)) % N + 1;
}
l--; r--;
assert(0 <= l && l < r && r < N);
m = solve(l, r);
printf("%lld\n", m);
}
}
static void input() {
scanf("%d%d", &N, &Q);
for(auto i = 0; i < N; i++) {
scanf("%u", A + i);
for(auto j = 0; j < B; j++) if((A[i] >> j & 1) == 0) Z[j].push_back(i);
}
for(auto i = N; --i >= 0; ) {
R[i] = A[i] ^ R[i + 1];
auto u = (uint)1;
for(auto j = B; --j >= 0; ) {
u = (u << 1) | (R[i] >> j & 1);
T.emplace_back(u, i);
}
}
sort(begin(T), end(T));
}
int main() {
input();
solve();
return 0;
}
Submission Info
Submission Time
2015-10-16 20:34:44+0900
Task
J - XORAND
User
arosusti
Language
C++11 (GCC 4.8.1)
Score
0
Code Size
2754 Byte
Status
TLE
Exec Time
4042 ms
Memory
46668 KB
Compile Error
./Main.cpp: In function ‘void input()’:
./Main.cpp:102: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:104:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%u", A + i);
^
./Main.cpp: In function ‘void solve()’:
./Main.cpp:89: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
65 ms
1004 KB
subtask0_sample_02.txt
AC
29 ms
944 KB
subtask1_pow2_01_mini.txt
AC
137 ms
1456 KB
subtask1_pow2_02_mini.txt
AC
142 ms
1456 KB
subtask1_pow2_03_OnlyOneLargeSeg.txt
TLE
4041 ms
41056 KB
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt
TLE
4040 ms
41240 KB
subtask1_pow2_05_UniqueLargeSegs.txt
TLE
4038 ms
38012 KB
subtask1_pow2_06_randomSegs.txt
TLE
4041 ms
41200 KB
subtask1_pow2_07_randomSegs.txt
TLE
4038 ms
41040 KB
subtask1_pow2_08_randomSegs.txt
TLE
4039 ms
41048 KB
subtask1_pow2_09_x_to_N-x_SegsOnly.txt
TLE
4040 ms
41040 KB
subtask1_pow2_10_x_to_N_SegsOnly.txt
TLE
4041 ms
41044 KB
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt
TLE
4040 ms
41292 KB
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt
TLE
4040 ms
41228 KB
subtask1_random_01.txt
TLE
4042 ms
46668 KB
subtask1_random_02.txt
TLE
4041 ms
46576 KB
subtask1_result_minmax_01.txt
AC
28 ms
1036 KB
subtask1_result_minmax_02.txt
AC
27 ms
1044 KB
subtask1_result_minmax_03.txt
AC
29 ms
936 KB