oj.uz

Submission #638496

# Submission time Handle Problem Language Result Execution time Memory
638496 2022-09-06T09:34:03 Z gagik_2007 XORanges (eJOI19_xoranges) C++17
100 / 100
 519 ms 16084 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef double ld;
typedef int itn;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll SAFEINF = 1e12;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 2e5 + 7;
ll n, m, k;
ll tz[800007];
ll tk[800007];
ll a[200007];

void buildz(int v, int tl, int tr) {
	if (tl == tr) {
		if (tl % 2 == 0) {
			tz[v] = a[tl];
		}
		else tz[v] = 0;
	}
	else {
		int tm = (tl + tr) / 2;
		buildz(2 * v, tl, tm);
		buildz(2 * v + 1, tm + 1, tr);
		tz[v] = tz[2 * v] ^ tz[2 * v + 1];
	}
}

void buildk(int v, int tl, int tr) {
	if (tl == tr) {
		if (tl % 2 == 1) {
			tk[v] = a[tl];
		}
		else tk[v] = 0;
	}
	else {
		int tm = (tl + tr) / 2;
		buildk(2 * v, tl, tm);
		buildk(2 * v + 1, tm + 1, tr);
		tk[v] = tk[2 * v] ^ tk[2 * v + 1];
	}
}

void updatez(int v, int tl, int tr, int ind, ll val) {
	if (tl == tr) {
		tz[v] = val;
	}
	else {
		int tm = (tl + tr) / 2;
		if (ind <= tm) {
			updatez(2 * v, tl, tm, ind, val);
		}
		else updatez(2 * v + 1, tm + 1, tr, ind, val);
		tz[v] = tz[2 * v] ^ tz[2 * v + 1];
	}
}

void updatek(int v, int tl, int tr, int ind, ll val) {
	if (tl == tr) {
		tk[v] = val;
	}
	else {
		int tm = (tl + tr) / 2;
		if (ind <= tm) {
			updatek(2 * v, tl, tm, ind, val);
		}
		else updatek(2 * v + 1, tm + 1, tr, ind, val);
		tk[v] = tk[2 * v] ^ tk[2 * v + 1];
	}
}

ll sumz(int v, int tl, int tr, int l, int r) {
	if (l > r)return 0;
	if (tl >= l && tr <= r)return tz[v];
	else {
		int tm = (tl + tr) / 2;
		return sumz(2 * v, tl, tm, l, min(tm, r)) ^
			sumz(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
	}
}

ll sumk(int v, int tl, int tr, int l, int r) {
	if (l > r)return 0;
	if (tl >= l && tr <= r)return tk[v];
	else {
		int tm = (tl + tr) / 2;
		return sumk(2 * v, tl, tm, l, min(tm, r)) ^
			sumk(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	buildk(1, 0, n - 1);
	buildz(1, 0, n - 1);
	for (int i = 0; i < k; i++) {
		int tp;
		ll x, y;
		cin >> tp >> x >> y;
		if (tp == 1) {
			x--;
			if (x % 2 == 0) {
				updatez(1, 0, n - 1, x, y);
			}
			else updatek(1, 0, n - 1, x, y);
		}
		else {
			x--, y--;
			if ((y - x + 1) % 2 == 0) {
				cout << 0 << endl;
			}
			else {
				if (x % 2 == 0) {
					cout << sumz(1, 0, n - 1, x, y) << endl;
				}
				else cout << sumk(1, 0, n - 1, x, y) << endl;
			}
		}
	}
	return 0;
}

/*
4 20
2
3
2
2

*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 9 ms 596 KB Output is correct
12 Correct 9 ms 616 KB Output is correct
13 Correct 11 ms 596 KB Output is correct
14 Correct 14 ms 628 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 13620 KB Output is correct
2 Correct 505 ms 16084 KB Output is correct
3 Correct 493 ms 16076 KB Output is correct
4 Correct 473 ms 15892 KB Output is correct
5 Correct 478 ms 15880 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 9 ms 596 KB Output is correct
12 Correct 9 ms 616 KB Output is correct
13 Correct 11 ms 596 KB Output is correct
14 Correct 14 ms 628 KB Output is correct
15 Correct 519 ms 13620 KB Output is correct
16 Correct 505 ms 16084 KB Output is correct
17 Correct 493 ms 16076 KB Output is correct
18 Correct 473 ms 15892 KB Output is correct
19 Correct 478 ms 15880 KB Output is correct
20 Correct 381 ms 15820 KB Output is correct
21 Correct 385 ms 15792 KB Output is correct
22 Correct 402 ms 15820 KB Output is correct
23 Correct 474 ms 15764 KB Output is correct
24 Correct 470 ms 15836 KB Output is correct