oj.uz

Submission #650332

# Submission time Handle Problem Language Result Execution time Memory
650332 2022-10-13T13:47:33 Z Kenpar XORanges (eJOI19_xoranges) C++17
100 / 100
 135 ms 9204 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl '\n'

const ll MOD = 1e9+7;
const ll INF = 1e16;
const int INT_INF = 1e9;
const ll MAX = 2e5+1;

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

void build(int v, int l, int r, int *arr, bool odd){
	int* cur = (odd? t1 : t2);

	if(l == r){
		l*=2;
		l+=!odd;
		cur[v] = arr[l];
		return;
	}

	int mid = (l+r) >> 1;

	build(v*2, l, mid, arr, odd);

	build(v*2+1, mid+1, r, arr, odd);

	cur[v] = cur[v*2] ^ cur[v*2+1];
}

int getXOR(int v, int tl, int tr, int l, int r, bool odd){
	
	int* cur = (odd? t1 : t2);

	if(tl > r || l >  tr) return 0;

	if(tl >= l && tr <= r){
		//cout<<tl<<" "<<tr<<endl;
		return cur[v];
	}

	int mid = (tr+tl) >> 1;

	return getXOR(v*2, tl, mid, l, min(mid, r), odd) ^ getXOR(v*2+1, mid+1, tr, max(mid+1, l), r, odd);
}

void modify(int v, int l, int r, int pos, int val, bool odd){
	int* cur = (odd? t1 : t2);

	if(l == r){
		cur[v] = val;
		return;
	}

	int mid = (l+r) >> 1;

	if(pos<=mid)
		modify(v*2, l, mid, pos, val, odd);
	else
		modify(v*2+1, mid+1, r, pos, val, odd);

	cur[v] = cur[v*2] ^ cur[v*2+1];
}

void solve(){
	int n,q;
	cin>>n>>q;

	int arr[n];

	for(int i = 0; i < n; i++) cin>>arr[i];

	build(1, 0, n/2-1, arr, false);
	build(1, 0, n/2, arr, true);

	while(q--){
		int a,b,c;
		cin>>a>>b>>c;

		
		if(a == 2){
			int temp = b;
			
			int ans = 0;
			bool odd = (c - b + 1) % 2;
			b = (b-1) / 2;
			c = (c-1) / 2;
			if(odd)
				ans = getXOR(1, 0, n/2 + (temp%2 - 1), b, c, temp%2);

			cout<<ans<<endl;
		}else{
			modify(1, 0, n/2 + (b%2 - 1), (b-1) / 2, c, b%2);
		}
	}
}
 
 
int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(NULL);
	int t = 1;
 
	//cin >> t;
 
	while(t--){
		solve();
		cout<<endl;
	}
}

Subtask #1
12.0 / 12.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 1 ms 340 KB Output is correct
5 Correct 1 ms 212 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #3
25.0 / 25.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 1 ms 340 KB Output is correct
5 Correct 1 ms 212 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 5196 KB Output is correct
2 Correct 128 ms 9136 KB Output is correct
3 Correct 135 ms 9204 KB Output is correct
4 Correct 118 ms 8792 KB Output is correct
5 Correct 116 ms 8852 KB Output is correct

Subtask #5
25.0 / 25.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 1 ms 340 KB Output is correct
5 Correct 1 ms 212 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 123 ms 5196 KB Output is correct
16 Correct 128 ms 9136 KB Output is correct
17 Correct 135 ms 9204 KB Output is correct
18 Correct 118 ms 8792 KB Output is correct
19 Correct 116 ms 8852 KB Output is correct
20 Correct 120 ms 8908 KB Output is correct
21 Correct 124 ms 8876 KB Output is correct
22 Correct 131 ms 9036 KB Output is correct
23 Correct 124 ms 8728 KB Output is correct
24 Correct 128 ms 8748 KB Output is correct