Submission #947405

#TimeUsernameProblemLanguageResultExecution timeMemory
947405GrandTiger1729Simple game (IZhO17_game)C++17
100 / 100
349 ms96956 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; struct SegTree { int l, r, mid; SegTree *lc, *rc; int val = 0; SegTree(int l_, int r_) : l(l_), r(r_) { mid = (l + r) / 2; if (l == r - 1) { return; } lc = new SegTree(l, mid); rc = new SegTree(mid, r); } void add(int ll, int rr, int u) { if (ll <= l && rr >= r) { val += u; return; } if (ll < mid) { lc->add(ll, rr, u); } if (mid < rr) { rc->add(ll, rr, u); } } int query(int i) { if (l == r - 1) { return val; } int ret = val; if (i < mid) { ret += lc->query(i); } else { ret += rc->query(i); } return ret; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } SegTree st(0, N); auto add = [&](int l, int r, int u) { if (l > r) { swap(l, r); } st.add(l, r, u); }; for (int i = 1; i < n; i++) { add(a[i - 1], a[i], 1); } while (q--) { int op; cin >> op; if (op == 1) { int i, x; cin >> i >> x; i--; if (i > 0) { add(a[i - 1], a[i], -1); } if (i + 1 < n) { add(a[i], a[i + 1], -1); } a[i] = x; if (i > 0) { add(a[i - 1], a[i], 1); } if (i + 1 < n) { add(a[i], a[i + 1], 1); } } else { int x; cin >> x; int ans = st.query(x); cout << ans << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...