Submission #1025845

#TimeUsernameProblemLanguageResultExecution timeMemory
1025845phoenixSimple game (IZhO17_game)C++17
100 / 100
186 ms19656 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100100; const int M = 200200; struct FenwickTree { int st[M] = {}; void update(int pos, int val) { for (; pos < M; pos += (pos & -pos)) st[pos] += val; } int get(int pos) { int res = 0; for (; pos; pos -= (pos & -pos)) res += st[pos]; return res; } }; FenwickTree Ox, Oy, XY; int n, m; int h[N]; vector<vector<int>> queries; int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // ios::sync_with_stdio(0); // cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> h[i]; } for (int i = 0; i < m; i++) { int tp; cin >> tp; if (tp == 1) { int pos, val; cin >> pos >> val; pos--; queries.push_back({tp, pos, val}); } else { int H; cin >> H; queries.push_back({tp, H}); } } /* COMPRESS */ { map<int, int> mp; for (int i = 0; i < n; i++) mp[h[i]] = 1; for (int i = 0; i < m; i++) { mp[queries[i].back()] = 1; } int k = 1; for (auto &c : mp) c.second = k++; for (int i = 0; i < n; i++) h[i] = mp[h[i]]; for (int i = 0; i < m; i++) queries[i].back() = mp[queries[i].back()]; } for (int i = 0; i < n - 1; i++) { int x = h[i], y = h[i + 1]; Ox.update(x, +1); Oy.update(y, +1); XY.update(max(x, y), +1); } for (int i = 0; i < m; i++) { int t = queries[i][0]; if (t == 1) { int pos = queries[i][1], val = queries[i][2]; if (pos) { Ox.update(h[pos - 1], -1); Oy.update(h[pos], -1); XY.update(max(h[pos - 1], h[pos]), -1); } if (pos < n - 1) { Ox.update(h[pos], -1); Oy.update(h[pos + 1], -1); XY.update(max(h[pos], h[pos + 1]), -1); } h[pos] = val; if (pos) { Ox.update(h[pos - 1], +1); Oy.update(h[pos], +1); XY.update(max(h[pos - 1], h[pos]), +1); } if (pos < n - 1) { Ox.update(h[pos], +1); Oy.update(h[pos + 1], +1); XY.update(max(h[pos], h[pos + 1]), +1); } } else { int H = queries[i][1]; int ans = Ox.get(H) + Oy.get(H) - 2 * XY.get(H); cout << ans << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...