oj.uz

Submission #631697

# Submission time Handle Problem Language Result Execution time Memory
631697 2022-08-18T13:13:23 Z CyberCow XORanges (eJOI19_xoranges) C++17
100 / 100
 133 ms 11336 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <stack>
#include <deque>
using namespace std;
using ll = long long;
vector<int> v;
int s[800008];
int s1[800008];

void build(int p, int lp, int rp)
{
	if (lp == rp)
	{
		if(lp % 2 == 0)
		s[p] = v[lp];
		return;
	}
	int m = (lp + rp) >> 1;
	build(p * 2, lp, m);
	build(p * 2 + 1, m + 1, rp);
	s[p] = s[p * 2] ^ s[p * 2 + 1];
}

void update(int p, int lp, int rp, int ind, int x)
{
	if (lp == rp)
	{
		s[p] = x;
		return;
	}
	int m = (lp + rp) >> 1;
	if (ind <= m)
		update(p * 2, lp, m, ind, x);
	else
		update(p * 2 + 1, m + 1, rp, ind, x);
	s[p] = s[p * 2] ^ s[p * 2 + 1];
}

int get_ans(int p, int lp, int rp, int l, int r)
{
	if (l > r)
		return 0;
	if (lp == l && rp == r)
	{
		return s[p];
	}
	int m = (lp + rp) >> 1;
	return get_ans(p * 2, lp, m, l, min(r, m)) ^ get_ans(p * 2 + 1, m + 1, rp, max(l, m + 1), r);
}

void build1(int p, int lp, int rp)
{
	if (lp == rp)
	{
		if(lp % 2)
		s1[p] = v[lp];
		return;
	}
	int m = (lp + rp) >> 1;
	build1(p * 2, lp, m);
	build1(p * 2 + 1, m + 1, rp);
	s1[p] = s1[p * 2] ^ s1[p * 2 + 1];
}

void update1(int p, int lp, int rp, int ind, int x)
{
	if (lp == rp)
	{
		s1[p] = x;
		return;
	}
	int m = (lp + rp) >> 1;
	if (ind <= m)
		update1(p * 2, lp, m, ind, x);
	else
		update1(p * 2 + 1, m + 1, rp, ind, x);
	s1[p] = s1[p * 2] ^ s1[p * 2 + 1];
}

int get_ans1(int p, int lp, int rp, int l, int r)
{
	if (l > r)
		return 0;
	if (lp == l && rp == r)
	{
		return s1[p];
	}
	int m = (lp + rp) >> 1;
	return get_ans1(p * 2, lp, m, l, min(r, m)) ^ get_ans1(p * 2 + 1, m + 1, rp, max(l, m + 1), r);
}

void solve()
{
	int n, i, j, x, q, y;
	cin >> n >> q;
	for ( i = 0; i < n; i++)
	{
		cin >> x;
		v.push_back(x);
	}
	build(1, 0, n - 1);
	build1(1, 0, n - 1);
	int c;
	for ( i = 0; i < q; i++)
	{
		cin >> c >> x >> y;
		if (c == 1)
		{
			if ((x - 1) % 2 == 0)
				update(1, 0, n - 1, x - 1, y);
			else
				update1(1, 0, n - 1, x - 1, y);
			v[x - 1] = y;
		}
		else
		{
			if ((y - x) % 2 == 0)
			{
				if ((x - 1) % 2 == 0)
					cout << get_ans(1, 0, n - 1, x - 1, y - 1) << '\n';
				else
					cout << get_ans1(1, 0, n - 1, x - 1, y - 1) << '\n';
			}
			else
				cout << 0 << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--)
	{
		solve();
	}
	return 0;
}

Compilation message

xoranges.cpp: In function 'void solve()':
xoranges.cpp:106:12: warning: unused variable 'j' [-Wunused-variable]
  106 |  int n, i, j, x, q, y;
      |            ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 8456 KB Output is correct
2 Correct 128 ms 11332 KB Output is correct
3 Correct 118 ms 11336 KB Output is correct
4 Correct 110 ms 11036 KB Output is correct
5 Correct 108 ms 11036 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 600 KB Output is correct
15 Correct 133 ms 8456 KB Output is correct
16 Correct 128 ms 11332 KB Output is correct
17 Correct 118 ms 11336 KB Output is correct
18 Correct 110 ms 11036 KB Output is correct
19 Correct 108 ms 11036 KB Output is correct
20 Correct 126 ms 11040 KB Output is correct
21 Correct 115 ms 11128 KB Output is correct
22 Correct 117 ms 11072 KB Output is correct
23 Correct 109 ms 11016 KB Output is correct
24 Correct 118 ms 10988 KB Output is correct