oj.uz

Submission #990598

# Submission time Handle Problem Language Result Execution time Memory
990598 2024-05-30T17:04:13 Z tch1cherin Simple game (IZhO17_game) C++17
100 / 100
 74 ms 6424 KB 
#include <bits/stdc++.h>
using namespace std;
 
struct fenwick {
  int size;
  vector<int> tree;
 
  fenwick(int n) : size(n + 1), tree(n + 1) {}
 
  void modify(int i, int value) {
    for (i++; i < size; i += i & -i) {
      tree[i] += value;
    }
  }
 
  void update(int l, int r, int value) {
    modify(l, value);
    modify(r, -value);
  }
 
  int get(int r) {
    int answer = 0;
    for (++r; r > 0; r -= r & -r) {
      answer += tree[r];
    }
    return answer;
  }
};
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> h(N);
  for (int &value : h) {
    cin >> value;
  }
  vector<int> type(M), pos(M), val(M), H(M);
  for (int i = 0; i < M; i++) {
    cin >> type[i];
    if (type[i] == 1) {
      cin >> pos[i] >> val[i];
    } else {
      cin >> H[i];
    }
  }
  vector<int> diff;
  for (int value : h) {
    diff.push_back(value);
  }
  for (int value : H) {
    diff.push_back(value);
  }
  for (int value : val) {
    diff.push_back(value);
  }
  sort(diff.begin(), diff.end());
  diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
  for (int &value : h) {
    value = lower_bound(diff.begin(), diff.end(), value) - diff.begin();
  }
  for (int &value : H) {
    value = lower_bound(diff.begin(), diff.end(), value) - diff.begin();
  }
  for (int &value : val) {
    value = lower_bound(diff.begin(), diff.end(), value) - diff.begin();
  }
  fenwick bit(diff.size());
  auto Add = [&](int i, int sign) {
    if (i >= 0 && i < N - 1) {
      if (h[i] < h[i + 1]) {
        bit.update(h[i], h[i + 1], sign);
      } else {
        bit.update(h[i + 1], h[i], sign);
      }
    }
  };
  for (int i = 0; i < N - 1; i++) {
    Add(i, 1);
  }
  for (int i = 0; i < M; i++) {
    if (type[i] == 1) {
      pos[i]--;
      Add(pos[i] - 1, -1);
      Add(pos[i], -1);
      h[pos[i]] = val[i];
      Add(pos[i] - 1, 1);
      Add(pos[i], 1);
    } else {
      cout << bit.get(H[i]) << "\n";
    }
  }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 27 ms 4824 KB Output is correct
9 Correct 65 ms 6384 KB Output is correct
10 Correct 63 ms 6348 KB Output is correct
11 Correct 22 ms 5192 KB Output is correct
12 Correct 52 ms 5848 KB Output is correct
13 Correct 44 ms 5848 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 27 ms 4824 KB Output is correct
9 Correct 65 ms 6384 KB Output is correct
10 Correct 63 ms 6348 KB Output is correct
11 Correct 22 ms 5192 KB Output is correct
12 Correct 52 ms 5848 KB Output is correct
13 Correct 44 ms 5848 KB Output is correct
14 Correct 70 ms 6356 KB Output is correct
15 Correct 70 ms 6420 KB Output is correct
16 Correct 70 ms 6352 KB Output is correct
17 Correct 74 ms 6348 KB Output is correct
18 Correct 70 ms 6424 KB Output is correct