oj.uz

Submission #467216

# Submission time Handle Problem Language Result Execution time Memory
467216 2021-08-22T04:55:13 Z syrtin XORanges (eJOI19_xoranges) C++17
38 / 100
 198 ms 9196 KB 
/*author:	syrtin*/
#include <bits/stdc++.h>

#define pb push_back
#define all(v) v.begin(),v.end()
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair < int, int > pii;
typedef vector<int> vi;
typedef vector<long long> vll;

const int N = 2e5 + 1;
const ll MOD = 1e9 + 7;
const int inf = int(1e9);
const ll INF = ll(1e16);

ll x, l, r, tr[N * 4], od[N * 4], a[N], j;
void build(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		tr[v] = a[xl];
		return;
	}
	build(v * 2 + 1, xl, xl + (xr - xl) / 2), build(v * 2 + 2, xl + (xr - xl) / 2, xr);
	tr[v] = tr[v * 2 + 1] ^ tr[v * 2 + 2];
}
void bld(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		od[v] = a[xl * 2];
		return;
	}
	bld(v * 2 + 1, xl, xl + (xr - xl) / 2), bld(v * 2 + 2, xl + (xr - xl) / 2, xr);
	od[v] = od[v * 2 + 1] ^ od[v * 2 + 2];
}
void up(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		od[v] = x;
		return;
	}
	if(xl + (xr - xl) / 2 <= j)up(v * 2 + 2, xl + (xr - xl) / 2, xr);
	else up(v * 2 + 1, xl, xl + (xr - xl) / 2);
	od[v] = od[v * 2 + 1] ^ od[v * 2 + 2];
}
void upd(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		tr[v] = x;
		return;
	}
	if(xl + (xr - xl) / 2 <= j)upd(v * 2 + 2, xl + (xr - xl) / 2, xr);
	else upd(v * 2 + 1, xl, xl + (xr - xl) / 2);
	tr[v] = tr[v * 2 + 1] ^ tr[v * 2 + 2];
}
int get(int v, int xl, int xr) {
	if(xl >= l && r >= xr)return tr[v];
	if(xl >= r || l >= xr)return 0;
	return get(v * 2 + 1, xl, xl + (xr - xl) / 2) ^ get(v * 2 + 2, xl + (xr - xl) / 2, xr);
}
int gg(int v, int xl, int xr) {
	if(xl >= l && r >= xr)return od[v];
	if(xl >= r || l >= xr)return 0;
	return gg(v * 2 + 1, xl, xl + (xr - xl) / 2) ^ gg(v * 2 + 2, xl + (xr - xl) / 2, xr);
}
void SOLVE(/*WATLE*/) {
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	build(0, 0, n);
	bld(0, 0, (n + 1) / 2);
	while(q--) {
		int wt;
		cin >> wt;
		if(wt == 1) {
			cin >> j >> x;
			upd(0, 0, n);
			if(j % 2)j /= 2, up(0, 0, (n + 1) / 2);
		}
		else {
			cin >> l >> r;
			l--;
			if((r - l) % 2 == 0)cout << 0 << '\n';
			else {
				if(l % 2){
					int s = get(0, 0, n);
					l = l / 2 + 1, r /= 2;
					cout << int(s ^ int(gg(0, 0, (n + 1) / 2))) << '\n';
				}
				else {
					l = l / 2, r = r / 2 + 1;
					cout << gg(0, 0, (n + 1) / 2) << '\n';					
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int times = 1;
	//cin >> times;
    for(int i = 1; i <= times; i++) {
        //cout << "Case #" << t << ": ";
        SOLVE();
    }
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 9196 KB Output is correct
2 Correct 198 ms 9148 KB Output is correct
3 Correct 193 ms 9196 KB Output is correct
4 Correct 158 ms 9140 KB Output is correct
5 Correct 160 ms 9156 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -