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

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