Submission #673248

#TimeUsernameProblemLanguageResultExecution timeMemory
673248moday_morningSimple game (IZhO17_game)C++17
100 / 100
168 ms19744 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1'000'002; const int H = 1'000'000; int a[N], t[4 * N]; void update (int v, int vl, int vr, int l, int r, int val) { if (vl == l && r == vr) { t[v] += val; return; } int m = (vl + vr) / 2; if (l <= m) update (v * 2, vl, m, l, min (r, m), val); if (r > m) update (v * 2 + 1, m + 1, vr, max (m + 1, l), r, val); } int coutt (int v, int vl, int vr, int pos) { if (vl == vr) return t[v]; int m = (vl + vr) / 2; if (pos <= m) return t[v] + coutt (v * 2, vl, m, pos); return t[v] + coutt (v * 2 + 1, m + 1, vr, pos); } void solve() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; if (i != 0) { update (1, 1, H, min (a[i - 1], a[i]), max (a[i - 1], a[i]), 1); } } while (m--) { int type; cin >> type; if (type == 1) { int pos, val; cin >> pos >> val; pos--; if (pos != 0) { update (1, 1, H, min (a[pos - 1], a[pos]), max (a[pos - 1], a[pos]), -1); update (1, 1, H, min (a[pos - 1], val), max (a[pos - 1], val), 1); } if (pos != n - 1) { update (1, 1, H, min (a[pos + 1], a[pos]), max (a[pos + 1], a[pos]), -1); update (1, 1, H, min (a[pos + 1], val), max (a[pos + 1], val), 1); } a[pos] = val; } else { int h; cin >> h; cout << coutt (1, 1, H, h) << '\n'; } } } signed main() { // usaco("A"); ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...