Submission #991213

#	Time	Username	Problem	Language	Result	Execution time	Memory
991213		model_code	Gift Exchange (JOI24_ho_t4)	C++17	100 / 100	1099 ms	68100 KiB

Main

// O((N + Q) log N + Q log Q)
#include <bits/stdc++.h>

using namespace std;

template<class M>
class lazy_segtree {
    using S = typename M::S;
    using F = typename M::F;

    int _n, sz, log;
    vector<S> d;
    vector<F> lz;

    void update(int k) { d[k] = M::op(d[2 * k], d[2 * k + 1]); }

    void all_apply(int k, F f) {
        d[k] = M::mapping(f, d[k]);
        if (k < sz) lz[k] = M::composition(f, lz[k]);
    }

    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = M::id;
    }

public:
    constexpr lazy_segtree(const vector<S> &init) : _n(int(init.size())) {
        log = 0;
        while (1 << log < _n) log++;
        sz = 1 << log;
        d.assign(2 * sz, M::e);
        lz.assign(sz, M::id);
        for (int i = 0; i < _n; i++) d[sz + i] = init[i];
        for (int i = sz - 1; i >= 1; i--) update(i);
    }

    S prod(int l, int r) {
        assert(0 <= l and l <= r and r <= _n);

        l += sz, r += sz;

        for (int i = log; i >= 1; i--) {
            if ((l >> i) << i != l) push(l >> i);
            if ((r >> i) << i != r) push(r >> i);
        }

        S sl = M::e, sr = M::e;
        while (l < r) {
            if (l & 1) sl = M::op(sl, d[l++]);
            if (r & 1) sr = M::op(d[--r], sr);
            l >>= 1, r >>= 1;
        }

        return M::op(sl, sr);
    }

    void apply(int l, int r, F f) {
        assert(0 <= l and l <= r and r <= _n);

        l += sz, r += sz;

        for (int i = log; i >= 1; i--) {
            if ((l >> i) << i != l) push(l >> i);
            if ((r >> i) << i != r) push(r >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1, r >>= 1;
            }
            l = l2, r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if ((l >> i) << i != l) update(l >> i);
            if ((r >> i) << i != r) update(r >> i);
        }
    }
};

class M {
public:
    using S = int;

    static constexpr S e = -1e9;

    static constexpr S op(const S &l, const S &r) {
        return max(l, r);
    }

    using F = pair<bool, int>;

    static constexpr F id = {false, 0};

    static constexpr F composition(const F &g, const F &f) {
        return (g.first ? g : f);
    }

    static constexpr S mapping(const F &f, const S &x) {
        return (f.first ? f.second : x);
    }
};

template<typename T>
class BIT {
    int n;
    vector<T> val;

    T sum(int i) {
        T ret = 0;
        while (i > 0) {
            ret += val[i];
            i -= i & -i;
        }
        return ret;
    }

public:
    BIT(int n) : n(n), val(n + 1, 0) {}

    void add(int i, T x = 1) {
        assert(0 <= i and i < n);
        i++;
        while (i <= n) {
            val[i] += x;
            i += i & -i;
        }
    }

    // [l, r)
    T sum(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        return sum(r) - sum(l);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int &i: a) {
        cin >> i;
        --i;
    }
    for (int &i: b) {
        cin >> i;
        --i;
    }
    vector<int> lb(n), rb(n);
    {
        lazy_segtree<M> st(vector(2 * n, 0));
        for (int i = 0; i < n; i++) {
            lb[i] = st.prod(b[i], a[i] + 1);
            st.apply(b[i], a[i] + 1, {true, i + 1});
        }
    }
    {
        lazy_segtree<M> st(vector(2 * n, -n));
        for (int i = n - 1; i >= 0; i--) {
            rb[i] = -st.prod(b[i], a[i] + 1);
            st.apply(b[i], a[i] + 1, {true, -i});
        }
    }
    vector<vector<pair<int, int>>> add(n), del(n);
    for (int i = 0; i < n; i++) {
        add[lb[i]].emplace_back(i + 1, rb[i] + 1);
        del[i].emplace_back(i + 1, rb[i] + 1);
    }
    int q;
    cin >> q;
    vector<int> l(q), r(q);
    for (int i = 0; i < q; i++) {
        cin >> l[i] >> r[i];
        --l[i];
    }
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return l[i] < l[j]; });
    int it = 0;
    vector<bool> ans(q);
    BIT<int> bt(n + 2);
    for (int i = 0; i < n; i++) {
        for (auto [nl, nr]: add[i]) {
            bt.add(nl, 1);
            bt.add(nr, -1);
        }
        while (it < q and l[ord[it]] == i) {
            int now = ord[it++];
            ans[now] = !bt.sum(0, r[now] + 1);
        }
        for (auto [nl, nr]: del[i]) {
            bt.add(nl, -1);
            bt.add(nr, 1);
        }
    }
    for (int i = 0; i < q; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
}

• 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