Submission #1160847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160847		MisterReaper	Simple game (IZhO17_game)	C++20	100 / 100	62 ms	4032 KiB

game

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

struct Fenwick {
    int n;
    std::vector<int> tree;
    Fenwick(int n_) : n(n_), tree(n + 1) {}
    void init(int n_) {
        n = n_;
        tree.assign(n + 1, 0);
    }
    void modify(int p, int x) {
        for (p += 1; p <= n; p += p & -p) {
            tree[p] += x;
        }
    }
    int get(int p) {
        int res = 0;
        for (p += 1; p; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, Q;
    std::cin >> N >> Q;

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

    std::vector<int> vals(A.begin(), A.end());

    std::vector<std::array<int, 3>> qq(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> qq[i][0];
        if (qq[i][0] == 1) {
            std::cin >> qq[i][1] >> qq[i][2];
            --qq[i][1];
            vals.emplace_back(qq[i][2]);
        } else {
            std::cin >> qq[i][1];
            vals.emplace_back(qq[i][1]);
        }
    }

    int nvals;
    std::sort(vals.begin(), vals.end());
    vals.resize(nvals = int(std::unique(vals.begin(), vals.end()) - vals.begin()));

    for (int i = 0; i < N; ++i) {
        A[i] = std::lower_bound(vals.begin(), vals.end(), A[i]) - vals.begin();
    }
    for (int i = 0; i < Q; ++i) {
        if (qq[i][0] == 1) {
            qq[i][2] = std::lower_bound(vals.begin(), vals.end(), qq[i][2]) - vals.begin();
        } else {
            qq[i][1] = std::lower_bound(vals.begin(), vals.end(), qq[i][1]) - vals.begin();
        }
    }

    Fenwick fen(nvals + 1);
    for (int i = 0; i + 1 < N; ++i) {
        fen.modify(std::min(A[i], A[i + 1]), +1);
        fen.modify(std::max(A[i], A[i + 1]), -1);
    }

    for (int i = 0; i < Q; ++i) {
        if (qq[i][0] == 1) {
            for (int idx : {qq[i][1] - 1, qq[i][1]}) {
                if (0 <= idx && idx + 1 < N) {
                    fen.modify(std::min(A[idx], A[idx + 1]), -1);
                    fen.modify(std::max(A[idx], A[idx + 1]), +1);
                }
            }
            A[qq[i][1]] = qq[i][2];
            for (int idx : {qq[i][1] - 1, qq[i][1]}) {
                if (0 <= idx && idx + 1 < N) {
                    fen.modify(std::min(A[idx], A[idx + 1]), +1);
                    fen.modify(std::max(A[idx], A[idx + 1]), -1);
                }
            }
        } else {
            std::cout << fen.get(qq[i][1]) << '\n';
        }
    }

    return 0;
}

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