Submission #1139898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139898		VMaksimoski008	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1647 ms	160764 KiB

Main

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

struct segment_tree {
    int n;
    vector<int> tree;
    segment_tree(int _n) : n(_n), tree(4*n, 1e9) {}

    void update(int u, int tl, int tr, int t, int p, int v) {
        if(tl == tr) {
            if(t == 1) tree[u] = min(tree[u], v);
            else tree[u] = v;
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, t, p, v);
            else update(2*u+1, tm+1, tr, t, p, v);
            tree[u] = min(tree[2*u], tree[2*u+1]);
        }
    }

    int query(int u, int tl, int tr, int l, int r) {
        if(tl > r || l > tr) return 1e9;
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return min(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int t, int p, int v) { update(1, 1, n, t, p, v); }
    int query(int l, int r) { return query(1, 1, n, l, r); }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q; cin >> n;
    vector<int> a(n+1), b(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) cin >> b[i];

    vector<int> L(n+1), R(n+1, n+1);
    map<int, vector<ar<int, 2> > > mp;
    for(int i=1; i<=n; i++) {
        mp[b[i]].push_back({ i, 1 });
        mp[a[i]].push_back({ i, -1 });
    }

    set<int> st;
    for(auto [p, vec] : mp) {
        for(auto [id, t] : vec) {
            if(t == -1) continue;
            auto it = st.lower_bound(id);
            if(it != st.end()) {
                R[id] = min(R[id], *it);
                L[*it] = max(L[*it], id);
            }

            if(!st.empty() && *st.begin() < id) {
                it = --st.lower_bound(id);
                R[*it] = min(R[*it], id);
                L[id] = max(L[id], *it);
            }

            st.insert(id);
        }

        for(auto [id, t] : vec)
            if(t == -1) st.erase(id);
    }

    cin >> q;
    vector<int> ans(q+1);
    vector<pii> qus[n+1];

    for(int i=1; i<=q; i++) {
        int l, r; cin >> l >> r;
        qus[r].push_back({ l, i });
    }

    segment_tree sgt(n);
    priority_queue<pii, vector<pii>, greater<> > pq;
    for(int i=1; i<=n; i++) pq.push({ R[i], i });
    for(int i=1; i<=n; i++) sgt.update(1, i, L[i]);

    for(int i=1; i<=n; i++) {
        while(!pq.empty() && pq.top().first <= i) {
            auto [_, u] = pq.top(); pq.pop();
            sgt.update(2, u, 1e9);
        }

        for(auto [j, id] : qus[i])
            ans[id] = (sgt.query(j, i) >= j);
    }

    for(int i=1; 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