Submission #650332

#	Time	Username	Problem	Language	Result	Execution time	Memory
650332		Kenpar	XORanges (eJOI19_xoranges)	C++17	100 / 100	135 ms	9204 KiB

xoranges

#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 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25