Submission #637339

#	Time	Username	Problem	Language	Result	Execution time	Memory
637339		VitaliyFS	XORanges (eJOI19_xoranges)	C++17	100 / 100	153 ms	12948 KiB

xoranges

#include<bits/stdc++.h>

using namespace std;

#define fr first
#define sc second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

const ll INF = 2000000000000000007, DIM = 200007, DIM2 = 107, MAXN = 100007, MOD = 998244353 ;

ll tt, mid, res,f, q, a[DIM], b[DIM], d[DIM], used[DIM],  dp[DIM], y, type, ptr, root, cnt, sum, pos, h, p, sx,sy, id, testcase, curans, nn, split, n, m, x, k1, k2, changecnt,k,l,r,v,u, l1,r1,l2,r2;
bool flag, flag2;
char c;

struct segTree {
	ll t[4*DIM];

	void build(int v, int vl, int vr) {
		if(vl==vr){
			t[v]=a[vl];
			return;
		}
		int vm=(vl+vr)/2;
		build(v*2+1,vl,vm);
		build(v*2+2,vm+1,vr);
		t[v]=t[v*2+1]^t[v*2+2];
	}

	ll query(int v, int vl, int vr, int l, int r){
		if(vl > r || vr < l)return 0;
		if(vl >=l &&vr<=r) return t[v];

		int vm=(vl+vr)/2;
		return query(v*2+1,vl,vm,l,r)^query(v*2+2,vm+1,vr,l,r);
	}

	void modify(int v, int vl, int vr, int pos, ll x) {
		if(vl==vr) {
			t[v]=x;
			return;
		}
		int vm=(vl+vr)/2;
		if(pos<=vm)
			modify(v*2+1,vl,vm,pos,x);
		else modify(v*2+2,vm+1,vr,pos,x);
		t[v]=t[v*2+1]^t[v*2+2];
	}
};

segTree t[3];

void solve() {
	cin>>n>>q;
	for(int i=1;i<=n;i++) {cin>>a[i];b[i]=a[i];}
	for(int i=1;i<=n;i++){
		if(i%2==1)a[i]=b[i];
		else a[i]=0;
	}
	t[1].build(0,1,n);
	for(int i=1;i<=n;i++){
		if(i%2==0)a[i]=b[i];
		else a[i]=0;
	}
	t[2].build(0,1,n);
	for(int i=1;i<=q;i++){
		cin>>type>>l>>r;
		if(type==2) {
			if((r-l+1)%2==0)cout<<"0\n";
			else {
				if(l%2==1)cout<<t[1].query(0,1,n,l,r)<<'\n';
				else cout<<t[2].query(0,1,n,l,r)<<'\n';
			}
		} else {
			if(l%2==1)t[1].modify(0,1,n,l,r);
			else t[2].modify(0,1,n,l,r);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	tt=1;
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	//cin>>tt;
	while(tt--) {
		solve();
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25