Submission #941139

#TimeUsernameProblemLanguageResultExecution timeMemory
941139atomSimple game (IZhO17_game)C++17
100 / 100
248 ms43684 KiB
#include "bits/stdc++.h" // @JASPER'S BOILERPLATE using namespace std; using ll = long long; #ifdef JASPER #include "debug.h" #else #define debug(...) 166 #endif struct SegmentTree { int n; vector <int> f, lzy; SegmentTree(int _n) : n(_n), f((_n << 2) + 5), lzy((_n << 2) + 5) {}; int merge(int x, int y) { return (x + y); } void push(int x, int l, int r) { if (!lzy[x]) return; int m = (l + r) / 2; lzy[x << 1] += lzy[x]; f[x << 1] += lzy[x] * (m - l + 1); lzy[x << 1 | 1] += lzy[x]; f[x << 1 | 1] += lzy[x] * (r - m); lzy[x] = 0; } void upd(int x, int l, int r, int u, int v, int val) { if (l > v || r < u) return; if (u <= l && r <= v) { lzy[x] += val; f[x] += val * (r - l + 1); return; } int m = (l + r) >> 1; push(x, l, r); upd(x << 1, l, m, u, v, val); upd(x << 1 | 1, m + 1, r, u, v, val); f[x] = merge(f[x << 1], f[x << 1 | 1]); } int qry(int x, int l, int r, int u, int v) { if (l > v || r < u) return 0; if (u <= l && r <= v) return f[x]; int m = (l + r) >> 1; push(x, l, r); int ql = qry(x << 1, l, m, u, v); int qr = qry(x << 1 | 1, m + 1, r, u, v); return merge(ql, qr); } void upd(int l, int r, int val) { upd(1, 1, n, l, r, val); } int qry(int l, int r) { return qry(1, 1, n, l, r); } }; const int N = 1e6 + 5; signed main() { cin.tie(0) -> sync_with_stdio(0); int n, q; cin >> n >> q; vector <int> h(n + 5); vector <vector <int>> queries(q + 5); for (int i = 1; i <= n; ++i) cin >> h[i]; for (int i = 1; i <= q; ++i) { int cmd; cin >> cmd; if (cmd == 1) { int x, y; cin >> x >> y; queries[i] = {cmd, x, y}; } else { int x; cin >> x; queries[i] = {cmd, x}; } } vector <int> cnt(N); SegmentTree st(N); for (int i = 1; i <= n; ++i) cnt[h[i]]++; for (int i = 2; i <= n; ++i) { int l = h[i - 1], r = h[i]; if (l > r) swap(l, r); l++, r--; st.upd(l, r, 1); } for (int i = 1; i <= q; ++i) { // debug(queries[i]); int cmd = queries[i][0]; int x, y; if (cmd == 1) { x = queries[i][1]; y = queries[i][2]; cnt[h[x]]--; if (x > 1) { int l = h[x - 1], r = h[x]; if (l > r) swap(l, r); st.upd(l + 1, r - 1, -1); } if (x < n) { int l = h[x], r = h[x + 1]; if (l > r) swap(l, r); st.upd(l + 1, r - 1, -1); } h[x] = y; cnt[h[x]]++; if (x > 1) { int l = h[x - 1], r = h[x]; if (l > r) swap(l, r); st.upd(l + 1, r - 1, 1); } if (x < n) { int l = h[x], r = h[x + 1]; if (l > r) swap(l, r); st.upd(l + 1, r - 1, 1); } } else { x = queries[i][1]; ll ans = cnt[x] + st.qry(x, x); cout << ans << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...