Submission #1274073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274073		MisterReaper	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	902 ms	86752 KiB

Main

// File giftexc.cpp created on 29.09.2025 at 08:38:31
#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 inf = 1 << 30;

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)

struct segtree {
    struct node {
        int val;
        int lz;
        node(int val_ = 0, int lz_ = inf) : val(val_), lz(lz_) {}
        void modify(int x) {
            val = x;
            lz = x;
        }
    };
    node unite(const node& lhs, const node& rhs) {
        node res;
        res.val = std::max(lhs.val, rhs.val);
        return res;
    }
    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].lz != inf) {
            tree[lv].modify(tree[v].lz);
            tree[rv].modify(tree[v].lz);
            tree[v].lz = 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);
    }
    int get(int v, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) {
            return tree[v].val;
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            return get(lv, l, mid, ql, qr);
        } else if (mid + 1 <= ql) {
            return get(rv, mid + 1, r, ql, qr);
        } else {
            return std::max(get(lv, l, mid, ql, mid),
                            get(rv, mid + 1, r, mid + 1, qr));
        }
    }
    int get(int l, int r) {
        return get(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 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;
    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.get(B[i], A[i]);
            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.get(B[i], A[i]);
            seg.modify(B[i], A[i], -i);
        }
    }

    int Q;
    std::cin >> Q;

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

    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[qry[i][0]].emplace_back(i);
    }

    fenwick fen(2 * 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.get(qry[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