제출 #1244230

#제출 시각아이디문제언어결과실행 시간메모리
1244230borisAngelovSimple game (IZhO17_game)C++20
100 / 100
273 ms25932 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const int MAX = 1000000; int n, q; int a[maxn]; struct SegmentTree { long long tree[4 * MAX + 50]; int lazy[4 * MAX + 50]; void pushLazy(int node, int l, int r) { if (lazy[node] == 0) return; tree[node] += (1LL * lazy[node]) * (1LL * (r - l + 1)); if (l != r) { lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } void update(int node, int l, int r, int ql, int qr, int delta) { pushLazy(node, l, r); if (l > qr || r < ql) return; if (ql <= l && r <= qr) { lazy[node] += delta; pushLazy(node, l, r); return; } int mid = (l + r) / 2; update(2 * node, l, mid, ql, qr, delta); update(2 * node + 1, mid + 1, r, ql, qr, delta); tree[node] = tree[2 * node] + tree[2 * node + 1]; } int queryPoint(int node, int l, int r, int pos) { pushLazy(node, l, r); if (l == r) return tree[node]; int mid = (l + r) / 2; if (pos <= mid) return queryPoint(2 * node, l, mid, pos); else return queryPoint(2 * node + 1, mid + 1, r, pos); } void update(int l, int r, int delta) { if (l > r) swap(l, r); //cout << "add " << l << " " << r << " :: " << delta << endl; update(1, 1, MAX, l, r, delta); } int queryPoint(int pos) { return queryPoint(1, 1, MAX, pos); } }; SegmentTree tree; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i < n; ++i) { if (a[i] != a[i + 1]) { tree.update(a[i], a[i + 1], +1); } } while (q--) { int type; cin >> type; if (type == 1) { int pos, x; cin >> pos >> x; if (pos > 1 && a[pos] != a[pos - 1]) tree.update(a[pos], a[pos - 1], -1); if (pos < n && a[pos] != a[pos + 1]) tree.update(a[pos], a[pos + 1], -1); a[pos] = x; if (pos > 1 && a[pos] != a[pos - 1]) tree.update(a[pos], a[pos - 1], +1); if (pos < n && a[pos] != a[pos + 1]) tree.update(a[pos], a[pos + 1], +1); } else { int h; cin >> h; cout << tree.queryPoint(h) << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...