Submission #528337


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, p = l; ; ) {
		if(z[i] - p < B) {
			MAZ(ret, AND - query(X[r + 1], p + 1, z[i]));
		} else {
			MAZ(ret, AND - qquery(X[r + 1], H[l + 1], z[i]));
		}
		if(i == zn) break;
		AND &= A[z[i]];
		p = z[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 2307 Byte
Status AC
Exec Time 824 ms
Memory 114668 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:82: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:83: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:95: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
AC × 2
AC × 19
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 28 ms 996 KB
subtask0_sample_02.txt AC 27 ms 1048 KB
subtask1_pow2_01_mini.txt AC 32 ms 2100 KB
subtask1_pow2_02_mini.txt AC 31 ms 2088 KB
subtask1_pow2_03_OnlyOneLargeSeg.txt AC 818 ms 114648 KB
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt AC 652 ms 114604 KB
subtask1_pow2_05_UniqueLargeSegs.txt AC 703 ms 114668 KB
subtask1_pow2_06_randomSegs.txt AC 726 ms 114600 KB
subtask1_pow2_07_randomSegs.txt AC 736 ms 114604 KB
subtask1_pow2_08_randomSegs.txt AC 763 ms 114640 KB
subtask1_pow2_09_x_to_N-x_SegsOnly.txt AC 767 ms 114608 KB
subtask1_pow2_10_x_to_N_SegsOnly.txt AC 764 ms 114600 KB
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt AC 824 ms 114604 KB
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt AC 628 ms 114608 KB
subtask1_random_01.txt AC 581 ms 114612 KB
subtask1_random_02.txt AC 578 ms 114616 KB
subtask1_result_minmax_01.txt AC 27 ms 1048 KB
subtask1_result_minmax_02.txt AC 27 ms 1048 KB
subtask1_result_minmax_03.txt AC 27 ms 1048 KB