Submission #555464

#TimeUsernameProblemLanguageResultExecution timeMemory
555464ngpin04Simple game (IZhO17_game)C++14
100 / 100
51 ms6860 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } const int N = 1e6 + 5; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); int bit[N]; int a[N]; int n,q; void update(int pos, int val) { for (; pos < N; pos += pos & -pos) bit[pos] += val; } void update(int l, int r, int val) { if (l > r) swap(l, r); update(l, val); update(r + 1, -val); } int getval(int pos) { int res = 0; for (; pos; pos -= pos & -pos) res += bit[pos]; return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef ONLINE_JUDGE // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); #endif cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i < n; i++) update(a[i], a[i + 1], 1); while (q--) { int op; cin >> op; if (op == 1) { int pos, val; cin >> pos >> val; if (pos > 1) update(a[pos - 1], a[pos], -1); if (pos < n) update(a[pos], a[pos + 1], -1); a[pos] = val; if (pos > 1) update(a[pos - 1], a[pos], 1); if (pos < n) update(a[pos], a[pos + 1], 1); } else { int v; cin >> v; cout << getval(v) << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...