Submission #846001

#	Time	Username	Problem	Language	Result	Execution time	Memory
846001		zwezdinv	Simple game (IZhO17_game)	C++17	100 / 100	43 ms	6984 KiB

game

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
using ll = long long;

struct fenwick {
    int n;
    vector<int> tr;

    fenwick(int n) : n(n), tr(vector<int>(n, 0)) {}
    fenwick() = default;

    void upd(int k, int x) {
        for (; k < n; k = (k | (k + 1))) tr[k] += x;
    }

    int get(int k) {
        int res = 0;
        for (; k >= 0; k = (k & (k + 1)) - 1) res += tr[k];
        return res;
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

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

    int n;
    cin >> n;
    int q;
    cin >> q;
    vector<int> a(n);
    fenwick fenw((int)1e6 + 1);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int x = 0; x + 1 < n; ++x) {
        fenw.upd(min(a[x], a[x + 1]), 1);
        fenw.upd(max(a[x], a[x + 1]) + 1, -1);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            --x;
            if (x + 1 < n) {
                fenw.upd(min(a[x], a[x + 1]), -1);
                fenw.upd(max(a[x], a[x + 1]) + 1, 1);
            }
            if (x - 1 >= 0) {
                fenw.upd(min(a[x], a[x - 1]), -1);
                fenw.upd(max(a[x], a[x - 1]) + 1, 1);
            }
            a[x] = y;
            if (x + 1 < n) {
                fenw.upd(min(a[x], a[x + 1]), 1);
                fenw.upd(max(a[x], a[x + 1]) + 1, -1);
            }
            if (x - 1 >= 0) {
                fenw.upd(min(a[x], a[x - 1]), 1);
                fenw.upd(max(a[x], a[x - 1]) + 1, -1);
            }
        } else {
            int h;
            cin >> h;
            cout << fenw.get(h) << '\n';
        }
    }
}

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