Submission #631697

#	Time	Username	Problem	Language	Result	Execution time	Memory
631697		CyberCow	XORanges (eJOI19_xoranges)	C++17	100 / 100	133 ms	11336 KiB

xoranges

#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 (stderr)

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 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25