oj.uz

Submission #447266

# Submission time Handle Problem Language Result Execution time Memory
447266 2021-07-25T16:25:38 Z bigo XORanges (eJOI19_xoranges) C++14
0 / 100
 780 ms 24976 KB 
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
const int INF = 1e9, MOD = 1e9 + 7;
struct Seg {
	int val = INF;
	int l, r, mid; // responisble for [l,r)
	Seg* lp, * rp;
	Seg(int l, int r) : l(l), r(r), mid((l + r) / 2) {
		if (l + 1 < r) {
			lp = new Seg(l, mid);
			rp = new Seg(mid, r);
		}
	}
	void pull() {
		val = lp->val ^ rp->val;
	}
	void update(int i, int x) {
		if (l + 1 == r) {
			val = x;
			return;
		}
		if (i < mid) lp->update(i, x);
		else rp->update(i, x);
		pull();
	}
	int query(int a, int b) { // xor of [a,b)
		if (a >= r || b <= l) return 0; // [a,b) and [l,r) are disjoint
		if (a <= l && r <= b) return val; // [l,r) is inside [a,b)
		return lp->query(a, b) ^ rp->query(a, b);
	}
};

int main() {
	int n, q;
	cin >> n >> q;
	if (n % 2 == 0) {
		Seg seg(0, n / 2);
		Seg seg1(0, n / 2);
		int g;
		for (int i = 0; i < n; i++) {
			cin >> g;
			if ((i + 1) % 2 == 1) {
				seg1.update(i/2, g);
			}
			else
				seg.update(i/2, g);
		}
		while (q--) {
			int op;
			cin >> op;
			if (op == 1) {
				int i, j;
				cin >> i >> j;
				i--;
				if ((i + 1) % 2 == 1)
					seg1.update(i/2, j);
				else
					seg.update(i/2, j);
			}
			else {
				int l, r;
				cin >> l >> r;
				l--;
				if ((r - l) % 2 == 0)
					cout << 0 << endl;
				else {
					if ((l + 1) % 2 == 1) {
						cout << seg1.query(l / 2, r / 2 + 1) << endl;
					}
					else {
						cout << seg.query(l / 2, r / 2 + 1) << endl;
					}
				}
			}
		}
	}
	else {
		Seg seg(0, n / 2);
		Seg seg1(0, n / 2 + 1);
		int g;
		for (int i = 0; i < n; i++) {
			cin >> g;
			if ((i + 1) % 2 == 1) {
				seg1.update(i / 2, g);
			}
			else
				seg.update(i / 2, g);
		}
		while (q--) {
			int op;
			cin >> op;
			if (op == 1) {
				int i, j;
				cin >> i >> j;
				i--;
				if ((i + 1) % 2 == 1)
					seg1.update(i / 2, j);
				else
					seg.update(i / 2, j);
			}
			else {
				int l, r;
				cin >> l >> r;
				l--;
				if ((r - l) % 2 == 0)
					cout << 0 << endl;
				else {
					if ((l + 1) % 2 == 1) {
						cout << seg1.query(l / 2, r / 2 + 1) << endl;
					}
					else {
						cout << seg.query(l / 2, r / 2 + 1) << endl;
					}
				}
			}
		}
	}
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 780 ms 24976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -