oj.uz

Submission #1011617

# Submission time Handle Problem Language Result Execution time Memory
1011617 2024-06-30T21:29:05 Z ziyad_alharbi XORanges (eJOI19_xoranges) C++17
100 / 100
 84 ms 9296 KB 
#include<bits/stdc++.h>
using namespace std;
const int o = 131072;
vector<int>tr1(o * 2), tr2(o * 2);
void u1(int x, int v)
{
	x += o;
	tr1[x] = v;
	for (x /= 2; x > 0; x /= 2)
	{
		//cout << tr1[x * 2] << ' ' << tr1[x * 2 + 1] << '\n';
		tr1[x] = (tr1[x * 2] ^ tr1[x * 2 + 1]);
	}
}
void u2(int x, int v)
{
	x += o;
	tr2[x] = v;
	for (x /= 2; x > 0; x /= 2)
	{
		//cout << tr2[x * 2] << ' ' << tr2[x * 2 + 1] << '\n';
		tr2[x] = (tr2[x * 2] ^ tr2[x * 2 + 1]);
	}
}
int _q1(int l, int r, int ql, int qr, int v)
{
	if (l >= qr || r <= ql)return 0;
	else if (l >= ql && r <= qr)
	{
		return tr1[v];
	}
	else
	{
		int m = (l + r) / 2;
		int ll = _q1(l, m, ql, qr, v * 2), rr = _q1(m, r, ql, qr, v * 2 + 1);
		//cout << ll << ' ' << rr << '\n';
		return (ll ^ rr);
	}
}
int q1(int l, int r)
{
	return _q1(0, o, l, r, 1);
}
int _q2(int l, int r, int ql, int qr, int v)
{
	if (l >= qr || r <= ql)return 0;
	else if (l >= ql && r <= qr)
	{
		return tr2[v];
	}
	else
	{
		int m = (l + r) / 2;
		int ll = _q2(l, m, ql, qr, v * 2), rr = _q2(m, r, ql, qr, v * 2 + 1);
		//cout << ll << ' ' << rr << '\n';
		return (ll ^ rr);
	}
}
int q2(int l, int r)
{
	return _q2(0, o, l, r, 1);
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		int n, q;
		cin >> n >> q;
		int a[n + 1];
		for (int x = 0; x < n; x++)
		{
			cin >> a[x];
			if (x % 2)
			{
				u1(x / 2, a[x]);
			}
			else
			{
				u2(x / 2, a[x]);
			}
		}
		while (q--)
		{
			int t, l, r;
			cin >> t >> l >> r;
			l--;
			r--;
			if (t == 1)
			{
				r++;
				if (l % 2)
				{
					u1(l / 2, r);
				}
				else
				{
					u2(l / 2, r);
				}
			}
			else
			{
				if (l % 2 != r % 2)cout << "0\n";
				else if (l % 2)
				{
					cout << q1(l / 2, r / 2 + 1) << '\n';
				}
				else
				{
					cout << q2(l / 2, r / 2 + 1) << '\n';
				}
			}
		}
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 2392 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 3 ms 2540 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4448 KB Output is correct
2 Correct 83 ms 9292 KB Output is correct
3 Correct 84 ms 9296 KB Output is correct
4 Correct 76 ms 8784 KB Output is correct
5 Correct 80 ms 8788 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 2392 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 3 ms 2540 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 73 ms 4448 KB Output is correct
16 Correct 83 ms 9292 KB Output is correct
17 Correct 84 ms 9296 KB Output is correct
18 Correct 76 ms 8784 KB Output is correct
19 Correct 80 ms 8788 KB Output is correct
20 Correct 74 ms 9044 KB Output is correct
21 Correct 69 ms 9060 KB Output is correct
22 Correct 73 ms 8932 KB Output is correct
23 Correct 69 ms 8772 KB Output is correct
24 Correct 72 ms 8792 KB Output is correct