Submission #1148298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148298		MisterReaper	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	936 ms	84768 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int inf = 23232323;

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
    struct node {
        int val = 0;
        int lazy = inf;
        node() {}
        node(int x) : val(x) {}
        node(int x, int y) : val(x), lazy(y) {}
        void modify(int x) {
            val = x;
            lazy = x;
        }
    };
    node unite(const node lhs, const node rhs) {
        return {std::max(lhs.val, rhs.val), inf};
    }
    int n;
    std::vector<node> tree;
    segtree(int n_) : n(n_), tree(n << 1) {}
    void push(int v, int l, int r) {
        def;
        if (tree[v].lazy != inf) {
            tree[lv].modify(tree[v].lazy);
            tree[rv].modify(tree[v].lazy);
            tree[v].lazy = inf;
        }
    }
    void modify(int v, int l, int r, int ql, int qr, int x) {
        if (ql == l && r == qr) {
            tree[v].modify(x);
            return;
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            modify(lv, l, mid, ql, qr, x);
        } else if (mid + 1 <= ql) {
            modify(rv, mid + 1, r, ql, qr, x);
        } else {
            modify(lv, l, mid, ql, mid, x);
            modify(rv, mid + 1, r, mid + 1, qr, x);
        }
        tree[v] = unite(tree[lv], tree[rv]);
    }
    void modify(int l, int r, int x) {
        modify(0, 0, n - 1, l, r, x);
    }
    node query(int v, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) {
            return tree[v];
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            return query(lv, l, mid, ql, qr);
        } else if (mid + 1 <= ql) {
            return query(rv, mid + 1, r, ql, qr);
        } else {
            return unite(query(lv, l, mid, ql, mid),
                        query(rv, mid + 1, r, mid + 1, qr));
        }
    }
    node query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }
};

struct fenwick {
    int n;
    std::vector<int> tree;
    fenwick(int n_) : n(n_), tree(n + 1) {}
    void modify(int p, int x) {
        for (p += 1; p <= n; p += p & -p) {
            tree[p] += x;
        }
    }
    void modify(int l, int r, int x) {
        modify(l, +x);
        modify(r + 1, -x);
    }
    int query(int p) {
        int res = 0;
        for (p += 1; p; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
};

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

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

    std::vector<int> S(N), T(N);
    {
        segtree seg(2 * N);
        seg.modify(0, 2 * N - 1, -1);
        for (int i = 0; i < N; ++i) {
            S[i] = seg.query(B[i], A[i]).val;
            seg.modify(B[i], A[i], i);
        }
    }
    {
        segtree seg(2 * N);
        seg.modify(0, 2 * N - 1, -N);
        for (int i = N - 1; i >= 0; --i) {
            T[i] = -seg.query(B[i], A[i]).val;
            seg.modify(B[i], A[i], -i);
        }
    }

    debug(S, T);

    int Q;
    std::cin >> Q;
    std::vector<int> ans(Q);
    std::vector<std::array<int, 2>> QQ(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> QQ[i][0] >> QQ[i][1];
        --QQ[i][0], --QQ[i][1];
    }

    std::vector<std::vector<int>> add(N + 1), del(N + 1), ask(N + 1);
    for (int i = 0; i < N; ++i) {
        add[S[i] + 1].emplace_back(i);
        del[i].emplace_back(i);
    }
    for (int i = 0; i < Q; ++i) {
        ask[QQ[i][0]].emplace_back(i);
    }

    fenwick fen(N);
    for (int i = 0; i <= N; ++i) {
        for (auto j : add[i]) {
            fen.modify(j, T[j] - 1, +1);
        }
        for (auto j : ask[i]) {
            ans[j] = fen.query(QQ[j][1]) == 0;
        }
        for (auto j : del[i]) {
            fen.modify(j, T[j] - 1, -1);
        }
    }

    for (int i = 0; i < Q; ++i) {
        std::cout << (ans[i] ? "Yes" : "No") << '\n';
    }

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 12 / 12