Submission #448535

#TimeUsernameProblemLanguageResultExecution timeMemory
448535Tenis0206XORanges (eJOI19_xoranges)C++11
55 / 100
4 ms600 KiB
#include <bits/stdc++.h> using namespace std; struct arbore_de_intervale { int par,imp; }; arbore_de_intervale ai[200005]; int n,q,v[200005]; void update(int poz, int val, int nod, int a, int b) { if(a==b) { if(a%2==1) { ai[nod].imp = val; ai[nod].par = 0; } else { ai[nod].par = val; ai[nod].imp = 0; } return; } int mij = (a+b)>>1; if(poz<=mij) { update(poz,val,nod*2,a,mij); } else { update(poz,val,nod*2+1,mij+1,b); } ai[nod].par = (ai[nod*2].par ^ ai[nod*2+1].par); ai[nod].imp = (ai[nod*2].imp ^ ai[nod*2+1].imp); } int query(int qa, int qb, int paritate, int nod, int a, int b) { if(qa<=a && qb>=b) { if(paritate%2==0) { return ai[nod].par; } return ai[nod].imp; } int mij = (a+b)>>1; int rez1 = 0, rez2 = 0; if(qa<=mij) { rez1 = query(qa,qb,paritate,nod*2,a,mij); } if(qb>mij) { rez2 = query(qa,qb,paritate,nod*2+1,mij+1,b); } return (rez1 ^ rez2); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>q; for(int i=1; i<=n; i++) { cin>>v[i]; update(i,v[i],1,1,n); } for(int i=1; i<=q; i++) { int t; cin>>t; if(t==1) { int poz,val; cin>>poz>>val; update(poz,val,1,1,n); } else { int x,y; cin>>x>>y; if((y-x+1)%2==0) { cout<<0<<'\n'; continue; } if(x%2==1) { cout<<query(x,y,1,1,1,n)<<'\n'; } else { cout<<query(x,y,0,1,1,n)<<'\n'; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...