oj.uz

Submission #601086

# Submission time Handle Problem Language Result Execution time Memory
601086 2022-07-21T11:00:17 Z Fidan XORanges (eJOI19_xoranges) C++17
100 / 100
 638 ms 22100 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=(2e5)+10;
vector<ll> T1(4*N, 0);
vector<ll> T2(4*N, 0);

void upd(ll l, ll r, ll id, ll val, ll v, vector<ll> &T){
	if(l==id && r==l){
		T[v]=val;
		return;
	}
	ll mid=(l+r)/2;
	if(id<=mid) upd(l, mid, id, val, 2*v, T);
	else upd(mid+1, r, id, val, 2*v+1, T);
	T[v]=(T[2*v]^T[2*v+1]);
}

ll que(ll l, ll r, ll tl, ll tr, ll v, vector<ll> &T){
	if(l>r) return 0;
	if(l==tl && r==tr) return T[v];
	ll tm=(tl+tr)/2;
	return (que(l, min(tm, r), tl, tm, 2*v, T)^que(max(tm+1, l), r, tm+1, tr, 2*v+1, T));
}

int main(){
	ll n, q, i;
	cin>>n>>q;
	vector<ll> a(n+1, 0);
	vector<ll> b(n+1, 0);
	for(i=1; i<=n; i++){
		ll x;
		cin>>x;
		if(i%2==0){
			a[i]=x;
			upd(1, n, i, x, 1, T1);
		}
		else{
			b[i]=x;
			upd(1, n, i, x, 1, T2);
		}
	}
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			ll j, val;
			cin>>j>>val;
			if(j%2==0) upd(1, n, j, val, 1, T1);
			else upd(1, n, j, val, 1, T2);
		}
		else{
			ll l, r;
			cin>>l>>r;
			if((r-l)%2==1) cout<<0<<endl;
			else{
				if(l%2==0) cout<<que(l, r, 1, n, 1, T1)<<endl;
				else cout<<que(l, r, 1, n, 1, T2)<<endl;
			}
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12836 KB Output is correct
2 Correct 9 ms 12732 KB Output is correct
3 Correct 6 ms 12840 KB Output is correct
4 Correct 8 ms 12836 KB Output is correct
5 Correct 9 ms 12836 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 9 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 9 ms 12756 KB Output is correct
5 Correct 9 ms 12832 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12836 KB Output is correct
2 Correct 9 ms 12732 KB Output is correct
3 Correct 6 ms 12840 KB Output is correct
4 Correct 8 ms 12836 KB Output is correct
5 Correct 9 ms 12836 KB Output is correct
6 Correct 7 ms 12756 KB Output is correct
7 Correct 9 ms 12756 KB Output is correct
8 Correct 7 ms 12756 KB Output is correct
9 Correct 9 ms 12756 KB Output is correct
10 Correct 9 ms 12832 KB Output is correct
11 Correct 17 ms 13060 KB Output is correct
12 Correct 16 ms 12984 KB Output is correct
13 Correct 18 ms 13012 KB Output is correct
14 Correct 20 ms 13044 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 19968 KB Output is correct
2 Correct 596 ms 22100 KB Output is correct
3 Correct 605 ms 21888 KB Output is correct
4 Correct 572 ms 21620 KB Output is correct
5 Correct 577 ms 21612 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12836 KB Output is correct
2 Correct 9 ms 12732 KB Output is correct
3 Correct 6 ms 12840 KB Output is correct
4 Correct 8 ms 12836 KB Output is correct
5 Correct 9 ms 12836 KB Output is correct
6 Correct 7 ms 12756 KB Output is correct
7 Correct 9 ms 12756 KB Output is correct
8 Correct 7 ms 12756 KB Output is correct
9 Correct 9 ms 12756 KB Output is correct
10 Correct 9 ms 12832 KB Output is correct
11 Correct 17 ms 13060 KB Output is correct
12 Correct 16 ms 12984 KB Output is correct
13 Correct 18 ms 13012 KB Output is correct
14 Correct 20 ms 13044 KB Output is correct
15 Correct 638 ms 19968 KB Output is correct
16 Correct 596 ms 22100 KB Output is correct
17 Correct 605 ms 21888 KB Output is correct
18 Correct 572 ms 21620 KB Output is correct
19 Correct 577 ms 21612 KB Output is correct
20 Correct 498 ms 21660 KB Output is correct
21 Correct 449 ms 21696 KB Output is correct
22 Correct 488 ms 21696 KB Output is correct
23 Correct 541 ms 21624 KB Output is correct
24 Correct 557 ms 21576 KB Output is correct