Submission #464077

#TimeUsernameProblemLanguageResultExecution timeMemory
464077CyberCowXORanges (eJOI19_xoranges)C++17
55 / 100
563 ms5184 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <string> #include <cmath> #include <map> #include <unordered_map> #include <fstream> #include <iomanip> #include <iterator> #include <stack> using namespace std; using ll = long long; vector <int> v, anc; int s[800020]; void build(int p, int lp, int rp) { if (lp == rp) { s[p] = v[lp]; return; } int m = (lp + rp) / 2; build(p * 2, lp, m); build(p * 2 + 1, m + 1, rp); s[p] = s[p * 2] ^ s[p * 2 + 1]; } int getxor(int p, int lp, int rp, int l, int r) { if (l > r) return 0; if (lp == l && rp == r) return s[p]; int m = (lp + rp) / 2; return getxor(p * 2, lp, m, l, min(m, r)) ^ getxor(p * 2 + 1, m + 1, rp, max(m + 1, l), r); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q, i, j, x, ans = 0, c,y; cin >> n >> q; for ( i = 0; i < n; i++) { cin >> x; v.push_back(x); } if (n <= 5000 && q <= 5000) { ans = 0; for (i = 0; i < q; i++) { cin >> c >> x >> y; x--; y--; if (c == 1) { v[x] = y + 1; } else { int f = 0; for (j = x; j <= y; j++) { if (((j - x + 1) * (y - j + 1)) % 2) f = f ^ v[j]; } ans = f; cout << ans << '\n'; } } } else { build(1, 0, n - 1); for ( i = 0; i < q; i++) { cin >> c >> x >> y; x--; y--; cout << getxor(1, 0, n - 1, x, y) << endl; } } 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...