oj.uz

Submission #464888

# Submission time Handle Problem Language Result Execution time Memory
464888 2021-08-14T11:31:26 Z Tsovak XORanges (eJOI19_xoranges) C++14
55 / 100
 1000 ms 12376 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, sz;
};

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

node t[N * 4];

int t1[N * 4], t2[N * 4];

int qry1(int tl, int tr, int l, int r, int pos);

int qry2(int tl, int tr, int l, int r, int pos);

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.sz = a.sz + b.sz;
	if (a.sz % 2 == 1) {
		if (tr % 2 == 1) {
			res.ans = (res.ans ^ (qry1(1, n, m + 1, tr, 1)));
		}
		else {
			res.ans = (res.ans ^ (qry2(1, n, m + 1, tr, 1)));
		}
	}
	if (b.sz % 2 == 1) {
		if (tl % 2 == 1) {
			res.ans = (res.ans ^ (qry1(1, n, tl, m, 1)));
		}
		else {
			res.ans = (res.ans ^ (qry2(1, n, tl, m, 1)));
		}
	}
	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) {
			t1[pos] = a[tl];
			t2[pos] = 0;
		}
		else {
			t1[pos] = 0;
			t2[pos] = 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);
	t1[pos] = (t1[pos * 2] ^ t1[pos * 2 + 1]);
	t2[pos] = (t2[pos * 2] ^ t2[pos * 2 + 1]);
	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) {
			t1[pos] = x;
			t2[pos] = 0;
		}
		else {
			t1[pos] = 0;
			t2[pos] = 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);
	t1[pos] = (t1[pos * 2] ^ t1[pos * 2 + 1]);
	t2[pos] = (t2[pos * 2] ^ t2[pos * 2 + 1]);
	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);
}

int qry1(int tl, int tr, int l, int r, int pos)
{
	if (l > r) {
		return 0;
	}
	if (tl == l && tr == r) {
		return t1[pos];
	}

	int m = (tl + tr) / 2;
	return ((qry1(tl, m, l, min(m, r), pos * 2)) ^ (qry1(m + 1, tr, max(m + 1, l), r, pos * 2 + 1)));
}

int qry2(int tl, int tr, int l, int r, int pos)
{
	if (l > r) {
		return 0;
	}
	if (tl == l && tr == r) {
		return t2[pos];
	}

	int m = (tl + tr) / 2;
	return ((qry2(tl, m, l, min(m, r), pos * 2)) ^ (qry2(m + 1, tr, max(m + 1, l), r, pos * 2 + 1)));
}

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:350:9: warning: unused variable 'j' [-Wunused-variable]
  350 |  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 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 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 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 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 16 ms 716 KB Output is correct
12 Correct 16 ms 816 KB Output is correct
13 Correct 20 ms 716 KB Output is correct
14 Correct 26 ms 800 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 12376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 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 16 ms 716 KB Output is correct
12 Correct 16 ms 816 KB Output is correct
13 Correct 20 ms 716 KB Output is correct
14 Correct 26 ms 800 KB Output is correct
15 Execution timed out 1090 ms 12376 KB Time limit exceeded
16 Halted 0 ms 0 KB -