Submission #1133571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133571		JelalTkm	Simple game (IZhO17_game)	C++20	100 / 100	112 ms	18344 KiB

game

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e6 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

struct segtree {
 
  vector<int> tree;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, 0);
  }
 
  void build(vector<int> &a, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < (int) a.size())
        tree[x] = a[lx];
    } else {
      int m = (lx + rx) >> 1;
      build(a, 2 * x + 1, lx, m);
      build(a, 2 * x + 2, m, rx);
      tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }
  }
 
  void build(vector<int> &a) {
    init((int) a.size());
    build(a, 0, 0, size);
  }
 
  void set(int i, int v, int x, int lx, int rx) {
    if (rx - lx == 1) {
      tree[x] += v;
      return;
    }
    int m = (lx + rx) >> 1;
    if (i < m) {
      set(i, v, 2 * x + 1, lx, m);
    } else {
      set(i, v, 2 * x + 2, m, rx);
    }
    tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
  }
 
  void set(int i, int v) {
    set(i, v, 0, 0, size);
  }
 
  int sum(int l, int r, int x, int lx, int rx) {
    if (l >= rx || lx >= r) {
      return 0;
    }
    if (lx >= l && rx <= r) {
      return tree[x];
    }
    int m = (lx + rx) >> 1;
    int s1 = sum(l, r, 2 * x + 1, lx, m);
    int s2 = sum(l, r, 2 * x + 2, m, rx);
    return s1 + s2;
  }
 
  int sum(int l, int r) {
    return sum(l, r, 0, 0, size);
  }
};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }

    segtree st;
    st.init(N);
    for (int i = 0; i < n - 1; i++) {
      if (a[i] <= a[i + 1]) {
        st.set(a[i], 1);
        st.set(a[i + 1] + 1, -1);
      } else {
        st.set(a[i + 1], 1);
        st.set(a[i] + 1, -1);
      }
    }
    while (q--) {
      int tp;
      cin >> tp;
      if (tp == 1) {
        int pos, v;
        cin >> pos >> v;
        pos--;
        if (pos - 1 >= 0) {
          bool ok = 0;
          if (a[pos - 1] > a[pos])
            swap(a[pos - 1], a[pos]), ok = 1;
          st.set(a[pos - 1], -1);
          st.set(a[pos] + 1, 1);
          if (ok) swap(a[pos], a[pos - 1]);
        }
        if (pos + 1 < n) {
          bool ok = 0;
          if (a[pos + 1] < a[pos])
            swap(a[pos + 1], a[pos]), ok = 1;
          st.set(a[pos], -1);
          st.set(a[pos + 1] + 1, 1);
          if (ok) swap(a[pos], a[pos + 1]);
        }
        a[pos] = v;
        if (pos - 1 >= 0) {
          bool ok = 0;
          if (a[pos - 1] > a[pos])
            swap(a[pos - 1], a[pos]), ok = 1;
          st.set(a[pos - 1], 1);
          st.set(a[pos] + 1, -1);
          if (ok) swap(a[pos], a[pos - 1]);
        }
        if (pos + 1 < n) {
          bool ok = 0;
          if (a[pos + 1] < a[pos])
            swap(a[pos + 1], a[pos]), ok = 1;
          st.set(a[pos], 1);
          st.set(a[pos + 1] + 1, -1);
          if (ok) swap(a[pos], a[pos + 1]);
        }
      } else {
        int h;
        cin >> h;
        cout << st.sum(0, h + 1) << '\n';
      }
    }
  }

  return 0;
}

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