Submission #441415

#	Time	Username	Problem	Language	Result	Execution time	Memory
441415		RaresFelix	XORanges (eJOI19_xoranges)	C++17	100 / 100	178 ms	11204 KiB

xoranges

#include <bits/stdc++.h>
#define MAXN 817171
#ifdef AICI
#define cin fi
#endif // AICI
using namespace std;
#ifdef AICI
ifstream fi("a.in");
#endif // AICI
int A[MAXN], n, q;

struct AINT
{
	int V[MAXN];
	void _u(int u, int s, int d, int p, int v)
	{
		if(d < p || p < s)return;
		if(s==d){
			V[u] = v;
			return;
		}
		_u(u*2, s, (s+d)/2, p, v);
		_u(u*2+1, (s+d)/2+1, d, p, v);
		V[u] = V[u*2] ^ V[u*2+1];
	}
	int _q(int u, int s, int d, int l, int r)
	{
		if(d < l || r < s)return 0;
		if(l <= s && d <= r)return V[u];
		return _q(u*2, s, (s+d)/2, l, r) ^ _q(u*2+1, (s+d)/2+1, d, l, r);
	}
	void setup(int delta)
	{
		for(int i = 1; i + delta <= n; i += 2)
			_u(1, 1, n, i+delta, A[i+delta]);
	}
} Pare, Impare;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)
		cin >> A[i];
	Pare.setup(1);
	Impare.setup(0);
	int tip, a, b;
	for(int i = 1; i <= q; ++i){
		cin >> tip >> a >> b;
		if(tip == 1) {
			A[a] = b;
			if(a%2)Impare._u(1, 1, n, a, b);
			else Pare._u(1, 1, n, a, b);
		} else {
			if((a^b)&1){
				cout << "0\n";
			} else {
				if(a&1) cout << Impare._q(1, 1, n, a, b);
				else cout << Pare._q(1, 1, n, a, b);
				cout << "\n";
			}
		}
	}
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25