Submission #404474

#	Time	Username	Problem	Language	Result	Execution time	Memory
404474		rama_pang	Simple game (IZhO17_game)	C++17	100 / 100	149 ms	10744 KiB

game

#include <bits/stdc++.h>
using namespace std;

class SegTree {
 public:
  int sz;
  vector<int> tree;

  SegTree(int sz) : sz(sz), tree(2 * sz, 0) {}

  void Update(int l, int r, int v) {
    for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
      if (l & 1) tree[l++] += v;
      if (r & 1) tree[--r] += v;
    }
  }

  int Query(int p) {
    int res = 0;
    for (p += sz; p > 0; p /= 2) res += tree[p];
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  const int MAX = 1e6 + 5;
  SegTree seg(MAX);

  const auto Update = [&](int u, int v, int sgn) {
    if (min(u, v) < 0 || max(u, v) >= N) return;
    u = A[u], v = A[v];
    if (u > v) swap(u, v);
    seg.Update(u, v, sgn);
  };

  for (int i = 1; i < N; i++) {
    Update(i - 1, i, +1);
  }

  for (int q = 0; q < M; q++) {
    int t;
    cin >> t;
    if (t == 1) {
      int i, v;
      cin >> i >> v;
      i--;
      Update(i - 1, i, -1);
      Update(i, i + 1, -1);
      A[i] = v;
      Update(i - 1, i, +1);
      Update(i, i + 1, +1);
    } else if (t == 2) {
      int h;
      cin >> h;
      cout << seg.Query(h) << '\n';
    }
  }
  return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51