Submission #990598

#	Time	Username	Problem	Language	Result	Execution time	Memory
990598		tch1cherin	Simple game (IZhO17_game)	C++17	100 / 100	74 ms	6424 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51