oj.uz

Submission #464891

# Submission time Handle Problem Language Result Execution time Memory
464891 2021-08-14T11:37:37 Z Tsovak XORanges (eJOI19_xoranges) C++17
100 / 100
 593 ms 14916 KB 
// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clr(x) x.clear()

#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ft front
#define bk back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(x);
	return;
}

ll gcd(ll a, ll b)
{
	if (a > b) {
		swap(a, b);
	}
	if (a == 0) {
		return b;
	}
	if (a == b) {
		return a;
	}
	return gcd(b % a, a);
}

ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}

bool is_prime(ll a)
{
	ll i;
	for (i = 2; i * i <= a; i++) {
		if (a % i == 0) {
			return false;
		}
	}
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrt(a));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrt(a));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
		}
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_by_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if ((b & 1) == 1) {
			ans *= a;
			ans %= mod;
		}
		b >>= 1;
		a *= a;
		a %= mod;
	}
	return ans;
}

ll factorial(int a)
{
	int i;
	ll ans = 1;
	for (i = 2; i <= a; i++) {
		ans *= ll(i);
	}
	return ans;
}

ll factorial_by_mod(int a, ll mod)
{
	int i;
	ll ans = 1;
	for (i = 2; i <= a; i++) {
		ans *= i;
		ans %= mod;
	}
	return ans;
}

// -------------------- Solution -------------------- //

struct node
{
	int ans, xr, xr1, xr2, sz;
};

const int N = 200005;
int a[N];
int n;

node t[N * 4];

node merge(node a, node b, int tl, int m, int tr)
{
	node res;
	res.ans = (a.ans ^ b.ans);
	res.xr = (a.xr ^ b.xr);
	res.xr1 = (a.xr1 ^ b.xr1);
	res.xr2 = (a.xr2 ^ b.xr2);
	res.sz = a.sz + b.sz;
	if (a.sz % 2 == 1) {
		if (tr % 2 == 1) {
			res.ans ^= b.xr1;
		}
		else {
			res.ans ^= b.xr2;
		}
	}
	if (b.sz % 2 == 1) {
		if (tl % 2 == 1) {
			res.ans ^= a.xr1;
		}
		else {
			res.ans ^= a.xr2;
		}
	}
	return res;
}

void bld(int tl, int tr, int pos)
{
	if (tl == tr) {
		t[pos].ans = t[pos].xr = a[tl];
		t[pos].sz = 1;

		if (tl % 2 == 1) {
			t[pos].xr1 = a[tl];
			t[pos].xr2 = 0;
		}
		else {
			t[pos].xr1 = 0;
			t[pos].xr2 = a[tl];
		}
		return;
	}

	int m = (tl + tr) / 2;
	bld(tl, m, pos * 2);
	bld(m + 1, tr, pos * 2 + 1);

	t[pos] = merge(t[pos * 2], t[pos * 2 + 1], tl, m, tr);
	return;
}

void upd(int tl, int tr, int ind, int x, int pos)
{
	if (tl == tr) {
		t[pos].ans = t[pos].xr = x;

		if (tl % 2 == 1) {
			t[pos].xr1 = x;
			t[pos].xr2 = 0;
		}
		else {
			t[pos].xr1 = 0;
			t[pos].xr2 = x;
		}
		return;
	}

	int m = (tl + tr) / 2;
	if (ind <= m) {
		upd(tl, m, ind, x, pos * 2);
	}
	else {
		upd(m + 1, tr, ind, x, pos * 2 + 1);
	}

	t[pos] = merge(t[pos * 2], t[pos * 2 + 1], tl, m, tr);
	return;
}

node qry(int tl, int tr, int l, int r, int pos)
{
	if (tl == l && tr == r) {
		return t[pos];
	}

	int m = (tl + tr) / 2;
	if (r <= m) {
		return qry(tl, m, l, r, pos * 2);
	}
	if (l > m) {
		return qry(m + 1, tr, l, r, pos * 2 + 1);
	}
	return merge((qry(tl, m, l, m, pos * 2)), (qry(m + 1, tr, m + 1, r, pos * 2 + 1)), l, m, r);
}

void solve()
{
	int i, j;
	int q;
	int type, ind, x, l, r, res;
	cin >> n >> q;
	for (i = 1; i <= n; i++) {
		cin >> a[i];
	}
	bld(1, n, 1);
	for (i = 1; i <= q; i++) {
		cin >> type;
		if (type == 1) {
			cin >> ind >> x;
			upd(1, n, ind, x, 1);
		}
		else {
			cin >> l >> r;
			res = qry(1, n, l, r, 1).ans;
			cout << res << endl;
		}
	}
	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	//cout << db(clock()) / CLOCKS_PER_SEC << endl;

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Compilation message

xoranges.cpp: In function 'void solve()':
xoranges.cpp:316:9: warning: unused variable 'j' [-Wunused-variable]
  316 |  int i, j;
      |         ^

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 9 ms 672 KB Output is correct
12 Correct 9 ms 576 KB Output is correct
13 Correct 14 ms 588 KB Output is correct
14 Correct 12 ms 588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 12600 KB Output is correct
2 Correct 592 ms 14832 KB Output is correct
3 Correct 593 ms 14764 KB Output is correct
4 Correct 552 ms 14916 KB Output is correct
5 Correct 565 ms 14800 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 9 ms 672 KB Output is correct
12 Correct 9 ms 576 KB Output is correct
13 Correct 14 ms 588 KB Output is correct
14 Correct 12 ms 588 KB Output is correct
15 Correct 567 ms 12600 KB Output is correct
16 Correct 592 ms 14832 KB Output is correct
17 Correct 593 ms 14764 KB Output is correct
18 Correct 552 ms 14916 KB Output is correct
19 Correct 565 ms 14800 KB Output is correct
20 Correct 407 ms 14276 KB Output is correct
21 Correct 395 ms 14156 KB Output is correct
22 Correct 388 ms 14160 KB Output is correct
23 Correct 552 ms 14672 KB Output is correct
24 Correct 543 ms 14788 KB Output is correct