Submission #877732

#TimeUsernameProblemLanguageResultExecution timeMemory
877732HusaynSimple game (IZhO17_game)C++14
100 / 100
150 ms13112 KiB
#include <bits/stdc++.h> using namespace std; int const maxn = 1e6 + 9; int a[maxn]; int lazy[maxn << 2]; void push(int v, int l, int r) { if(l != r) { lazy[v << 1] += lazy[v]; lazy[v << 1 | 1] += lazy[v]; lazy[v] = 0; } } void updateRange(int v, int tl, int tr, int l, int r, int x) { if(tr < l || tl > r) { return; } push(v, tl, tr); if(l <= tl && tr <= r) { lazy[v] += x; push(v, tl, tr); return; } int tm = tl + tr >> 1; updateRange(v << 1, tl, tm, l, r, x); updateRange(v << 1 | 1, tm + 1, tr, l, r, x); } int get(int v, int tl, int tr, int k) { push(v, tl, tr); if(tl == tr) return lazy[v]; int tm = tl + tr >> 1; return k <= tm ? get(v << 1, tl, tm, k) : get(v << 1 | 1, tm + 1, tr, k); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m >> a[1]; for(int i = 2; i <= n; i ++) { cin >> a[i]; updateRange(1, 1, maxn - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1); } while(m --) { int t, i; cin >> t >> i; if(t == 2) { cout << get(1, 1, maxn - 1, i) << '\n'; continue; } int v; cin >> v; if(i > 1) { updateRange(1, 1, maxn - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]), -1); updateRange(1, 1, maxn - 1, min(a[i - 1], v), max(a[i - 1], v), 1); } if(i < n) { updateRange(1, 1, maxn - 1, min(a[i + 1], a[i]), max(a[i + 1], a[i]), -1); updateRange(1, 1, maxn - 1, min(a[i + 1], v), max(a[i + 1], v), 1); } a[i] = v; } return 0; }

Compilation message (stderr)

game.cpp: In function 'void updateRange(int, int, int, int, int, int)':
game.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
game.cpp: In function 'int get(int, int, int, int)':
game.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...