Submission #1018061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018061		ind1v	Simple game (IZhO17_game)	C++11	100 / 100	41 ms	6952 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int H = 1e6 + 5;

struct fenwick_tree {
  int f[H];
  
  fenwick_tree() {
    memset(f, 0, sizeof(f));
  }
  
  void upd(int i, int x) {
    for (; i < H; i += i & -i) {
      f[i] += x;
    }
  }
  
  void upd(int l, int r, int x) {
    upd(l, x);
    upd(r + 1, -x);
  }
  
  int get(int i) {
    int r = 0;
    for (; i > 0; i -= i & -i) {
      r += f[i];
    }
    return r;
  }
  
  int get(int l, int r) {
    return get(r) - get(l - 1);
  }
};

int n, m;
int h[N];
fenwick_tree ft;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    if (i >= 2) {
      ft.upd(min(h[i - 1], h[i]), max(h[i - 1], h[i]), 1);
    }
  }
  while (m--) {
    int t;
    cin >> t;
    if (t == 1) {
      int pos, val;
      cin >> pos >> val;
      if (pos > 1) {
        ft.upd(min(h[pos - 1], h[pos]), max(h[pos - 1], h[pos]), -1);
      }
      if (pos < n) {
        ft.upd(min(h[pos + 1], h[pos]), max(h[pos + 1], h[pos]), -1);
      }
      h[pos] = val;
      if (pos > 1) {
        ft.upd(min(h[pos - 1], h[pos]), max(h[pos - 1], h[pos]), +1);
      }
      if (pos < n) {
        ft.upd(min(h[pos + 1], h[pos]), max(h[pos + 1], h[pos]), +1);
      }
    } else if (t == 2) {
      int H;
      cin >> H;
      cout << ft.get(H) << '\n';
    }
  }
  return 0;
}

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