Submission #877161

#TimeUsernameProblemLanguageResultExecution timeMemory
877161__Davit__Simple game (IZhO17_game)C++17
100 / 100
250 ms11344 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ff first #define ss second #define pb push_back #define vr(v) v.begin(),v.end() #define rv(v) v.rbegin(),v.rend() #define Code ios_base::sync_with_stdio(false); #define By cin.tie(NULL); #define Davit cout.tie(NULL); const int MAXH = 1000000; using namespace std; //#include "algo/debug.h" vector<int> seg; int sz = 1; int get(int l, int r, int x, int index) { if (l == r) { return seg[x]; } int m = (l + r) >> 1; if (index <= m) { return seg[x] + get(l, m, x + x + 1, index); } else { return seg[x] + get(m + 1, r, x + x + 2, index); } } int get(int index) { return get(0, sz - 1, 0, index); } void add(int lx, int rx, int x, int l, int r, int val) { if (lx > r || rx < l)return; if (l <= lx && rx <= r) { seg[x] += val; return; } int m = (lx + rx) >> 1; add(lx, m, x + x + 1, l, r, val); add(m + 1, rx, x + x + 2, l, r, val); } void add(int l, int r, int val) { add(0, sz - 1, 0, l, r, val); } int main() { int n, m; cin >> n >> m; vector<int> v(n); for (int i = 0; i < n; i++)cin >> v[i]; while (sz < MAXH) { sz <<= 1; } seg.resize(sz + sz, 0); for (int i = 1; i < n; i++) { add(min(v[i - 1], v[i]), max(v[i - 1], v[i]), 1); } while (m--) { int type; cin >> type; if (type == 1) { int pos, val; cin >> pos >> val; pos--; if (pos) { add(min(v[pos - 1], v[pos]), max(v[pos - 1], v[pos]), -1); } if (pos < n - 1) { add(min(v[pos + 1], v[pos]), max(v[pos + 1], v[pos]), -1); } v[pos] = val; if (pos) { add(min(v[pos - 1], v[pos]), max(v[pos - 1], v[pos]), 1); } if (pos < n - 1) { add(min(v[pos + 1], v[pos]), max(v[pos + 1], v[pos]), 1); } } else { int H; cin >> H; cout << get(H) << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...