oj.uz

Submission #990583

# Submission time Handle Problem Language Result Execution time Memory
990583 2024-05-30T16:32:10 Z tch1cherin Simple game (IZhO17_game) C++17
0 / 100
 1 ms 604 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);
  }
  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();
  }
  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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -