Submission #769591

#TimeUsernameProblemLanguageResultExecution timeMemory
769591GordonRemzi007XORanges (eJOI19_xoranges)C++17
100 / 100
425 ms7896 KiB
#include <iostream> #include <vector> #include <cmath> using namespace std; class SegmentTree { int n, i = 0; vector<int> seggy; public: SegmentTree(int size):n(size) { seggy = vector<int>(2*n); } void push(int x) { seggy[n+i] = x; i++; } void build() { for(int i = n-1; i > 0; i--) seggy[i] = seggy[2*i]^seggy[2*i+1]; } void update(int x, int y) { x+=n; seggy[x] = y; while(x > 1) { x/=2; seggy[x] = seggy[2*x]^seggy[2*x+1]; } } int query(int x, int y) { int res = 0; for (x+=n, y+=n+1; x<y; x/=2, y/=2) { if (x&1) res ^= seggy[x++]; if (y&1) res ^= seggy[--y]; } return res; } }; int main() { int n, q, t, x, y; cin >> n >> q; SegmentTree S1(n/2), S2((n+1)/2); for(int i = 0; i < n; i++) { cin >> x; if(i%2) S1.push(x); else S2.push(x); } S1.build(); S2.build(); while(q--) { cin >> t >> x >> y; x--; if(t == 1) { if(x%2) S1.update((x-1)/2, y); else S2.update(x/2, y); } else { y--; if((y-x+1)%2 == 0) cout << "0\n"; else { if(x%2) cout << S1.query((x-1)/2, (y-1)/2) << "\n"; else cout << S2.query(x/2, y/2) << "\n"; } } } }
#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...