oj.uz

Submission #1011613

# Submission time Handle Problem Language Result Execution time Memory
1011613 2024-06-30T21:07:54 Z ziyad_alharbi XORanges (eJOI19_xoranges) C++17
55 / 100
 8 ms 3164 KB 
#include<bits/stdc++.h>
using namespace std;
const int o = (1 << (int)ceil(log(1e5)));
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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 528 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 528 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 644 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 3164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 528 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 528 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 644 KB Output is correct
15 Runtime error 8 ms 3164 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -