Submission #1160819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160819		MisterReaper	Simple game (IZhO17_game)	C++20	22 / 100	1092 ms	32076 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

constexpr int MAXV = int(1E7);

struct node {
    int sum;
    int lv;
    int rv;
    node() {}
    node(int a, int b, int c) : sum(a), lv(b), rv(c) {}
    node(const node& x) : sum(x.sum), lv(x.lv), rv(x.rv) {}
} tree[MAXV];
int node_alloc;
int new_node() {
    tree[node_alloc] = {0, -1, -1};
    return node_alloc++;
}
int new_node(int x) {
    tree[node_alloc] = tree[x];
    return node_alloc++;
}

int init(int l, int r) {
    if (l == r) {
        return new_node();
    }
    int v = new_node();
    int mid = (l + r) >> 1;
    tree[v].lv = init(l, mid);
    tree[v].rv = init(mid + 1, r);
    return v;
}

int modify(int v, int l, int r, int p) {
    if (l == r) {
        int nv = new_node(v);
        tree[nv].sum++;
        return nv;
    } 
    int mid = (l + r) >> 1;
    int nv = new_node(v);
    if (p <= mid) {
        tree[nv].lv = modify(tree[v].lv, l, mid, p);
        tree[nv].sum++;
    } else {
        tree[nv].rv = modify(tree[v].rv, mid + 1, r, p);
        tree[nv].sum++;
    }
    return nv;
}

int query(int v, int l, int r, int ql, int qr) {
    if (ql == l && r == qr) {
        return tree[v].sum;
    }
    int mid = (l + r) >> 1;
    if (qr <= mid) {
        return query(tree[v].lv, l, mid, ql, qr);
    } else if (mid + 1 <= ql) {
        return query(tree[v].rv, mid + 1, r, ql, qr);
    } else {
        return query(tree[v].lv, l, mid, ql, mid)
             + query(tree[v].rv, mid + 1, r, mid + 1, qr);
    }
}

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]);
        }
    }

    vals.emplace_back(-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();
        }
    }

    debug("wtf");

    constexpr int B = 3000;

    std::vector<int> roots(nvals + 1);
    auto construct = [&]() -> void {
        node_alloc = 0;
        std::vector<std::pair<int, int>> piivec;
        for (int i = 0; i + 1 < N; ++i) {
            piivec.emplace_back(std::min(A[i], A[i + 1]), std::max(A[i], A[i + 1]));
        }
        
        std::sort(piivec.begin(), piivec.end());

        roots[0] = init(0, nvals - 1);
        int pivot = 0;
        for (int i = 0; i < nvals; ++i) {
            roots[i + 1] = roots[i];
            while (pivot < piivec.size() && piivec[pivot].first == i) {
                roots[i + 1] = modify(roots[i + 1], 0, nvals - 1, piivec[pivot].second);
                pivot++;
            }
        }
    };

    std::vector<std::tuple<int, int, int>> changed;
    for (int l = 0; l < Q; l += B) {
        int r = std::min(Q, l + B);
        changed.clear();
        changed.reserve(4 * B);
        debug(l, r);
        construct();
        debug("???");
        for (int i = l; i < r; ++i) {
            if (qq[i][0] == 1) {
                for (int idx : {qq[i][1] - 1, qq[i][1]}) {
                    if (0 <= idx && idx + 1 < N) {
                        changed.emplace_back(std::min(A[idx], A[idx + 1]), 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) {
                        changed.emplace_back(std::min(A[idx], A[idx + 1]), std::max(A[idx], A[idx + 1]), +1);
                    }
                }
            } else {
                int ans = query(roots[qq[i][1]], 0, nvals - 1, qq[i][1], nvals - 1);
                debug(ans);
                for (auto[x, y, d] : changed) {
                    if (x <= qq[i][1] && qq[i][1] <= y) {
                        ans += d;
                    }
                }
                std::cout << ans << '\n';
            }
        }
    }

    return 0;
}

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