Submission #731845

#TimeUsernameProblemLanguageResultExecution timeMemory
731845stevancvSimple game (IZhO17_game)C++14
100 / 100
320 ms19460 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 1e6 + 2; const int inf = 2e9 + 2; int st[4 * N], lzy[4 * N]; void Propagate(int node, int l, int r) { if (lzy[node] == 0) return; if (l < r) { lzy[2 * node] += lzy[node]; lzy[2 * node + 1] += lzy[node]; } st[node] += lzy[node]; lzy[node] = 0; } void Add(int node, int l, int r, int ql, int qr, int x) { Propagate(node, l, r); if (r < ql || qr < l || ql > qr) return; if (ql <= l && r <= qr) { lzy[node] += x; Propagate(node, l, r); return; } int mid = l + r >> 1; Add(2 * node, l, mid, ql, qr, x); Add(2 * node + 1, mid + 1, r, ql, qr, x); st[node] = max(st[2 * node], st[2 * node + 1]); } int Get(int node, int l, int r, int x) { Propagate(node, l, r); if (l == r) return st[node]; int mid = l + r >> 1; if (x <= mid) return Get(2 * node, l, mid, x); return Get(2 * node + 1, mid + 1, r, x); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++) { int manji = min(a[i - 1], a[i]); int veci = max(a[i - 1], a[i]); Add(1, 1, N, manji + 1, veci - 1, 1); } while (q--) { int ty; cin >> ty; if (ty == 2) { int x; cin >> x; cout << Get(1, 1, N, x) << en; continue; } int i, manji, veci; cin >> i; i -= 1; if (i > 0) { manji = min(a[i - 1], a[i]); veci = max(a[i - 1], a[i]); Add(1, 1, N, manji + 1, veci - 1, -1); } if (i < n - 1) { manji = min(a[i], a[i + 1]); veci = max(a[i], a[i + 1]); Add(1, 1, N, manji + 1, veci - 1, -1); } cin >> a[i]; if (i > 0) { manji = min(a[i - 1], a[i]); veci = max(a[i - 1], a[i]); Add(1, 1, N, manji + 1, veci - 1, 1); } if (i < n - 1) { manji = min(a[i], a[i + 1]); veci = max(a[i], a[i + 1]); Add(1, 1, N, manji + 1, veci - 1, 1); } } return 0; }

Compilation message (stderr)

game.cpp: In function 'void Add(int, int, int, int, int, int)':
game.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
game.cpp: In function 'int Get(int, int, int, int)':
game.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...