oj.uz

Submission #507304

# Submission time Handle Problem Language Result Execution time Memory
507304 2022-01-12T10:44:46 Z MilosMilutinovic Simple game (IZhO17_game) C++14
100 / 100
 180 ms 11120 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int st[N * 4];

void modify(int node, int l, int r, int ll, int rr, int x) {
  if (l > r || l > rr || r < ll) return;
  if (ll <= l && r <= rr) {
    st[node] += x;
    return;
  }
  int mid = l + r >> 1;
  modify(node * 2, l, mid, ll, rr, x);
  modify(node * 2 + 1, mid + 1, r, ll, rr, x);
}

int get(int node, int l, int r, int x) {
  if (l == r) return st[node];
  int mid = l + r >> 1;
  if (x <= mid) return st[node] + get(node * 2, l, mid, x);
  else return st[node] + get(node * 2 + 1, mid + 1, r, x);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  auto Add = [&](int i) {
    if (i < 0 || i >= n - 1) return;
    int L = min(h[i], h[i + 1]);
    int R = max(h[i], h[i + 1]);
    modify(1, 1, N, L, R, 1);
  };
  auto Rem = [&](int i) {
    if (i < 0 || i >= n - 1) return;
    int L = min(h[i], h[i + 1]);
    int R = max(h[i], h[i + 1]);
    modify(1, 1, N, L, R, -1);
  };
  for (int i = 0; i + 1 < n; i++) {
    Add(i);
  }
  while (q--) {
    int foo;
    cin >> foo;
    if (foo == 1) {
      int pos, val;
      cin >> pos >> val;
      --pos;
      Rem(pos);
      Rem(pos - 1);
      h[pos] = val;
      Add(pos);
      Add(pos - 1);
    } else {
      int H;
      cin >> H;
      cout << get(1, 1, N, H) << '\n';
    }
  }
  return 0;
}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/

Compilation message

game.cpp: In function 'void modify(int, int, int, int, int, int)':
game.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |   int mid = l + r >> 1;
      |             ~~^~~
game.cpp: In function 'int get(int, int, int, int)':
game.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 4 ms 6476 KB Output is correct
5 Correct 4 ms 6476 KB Output is correct
6 Correct 4 ms 6604 KB Output is correct
7 Correct 2 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 4 ms 6476 KB Output is correct
5 Correct 4 ms 6476 KB Output is correct
6 Correct 4 ms 6604 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 41 ms 1608 KB Output is correct
9 Correct 82 ms 11076 KB Output is correct
10 Correct 86 ms 11072 KB Output is correct
11 Correct 34 ms 1612 KB Output is correct
12 Correct 65 ms 2916 KB Output is correct
13 Correct 53 ms 2828 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 4 ms 6476 KB Output is correct
5 Correct 4 ms 6476 KB Output is correct
6 Correct 4 ms 6604 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 41 ms 1608 KB Output is correct
9 Correct 82 ms 11076 KB Output is correct
10 Correct 86 ms 11072 KB Output is correct
11 Correct 34 ms 1612 KB Output is correct
12 Correct 65 ms 2916 KB Output is correct
13 Correct 53 ms 2828 KB Output is correct
14 Correct 158 ms 11068 KB Output is correct
15 Correct 165 ms 11072 KB Output is correct
16 Correct 151 ms 11076 KB Output is correct
17 Correct 154 ms 11120 KB Output is correct
18 Correct 180 ms 11096 KB Output is correct