Submission #1357636

#TimeUsernameProblemLanguageResultExecution timeMemory
1357636gayGift Exchange (JOI24_ho_t4)C++20
100 / 100
2409 ms117752 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const int INF = 1e9, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

struct seg_tree {
    struct Node {
        int mx = -INF, dept = -INF;
    };
    vector<Node> tree;
    void push(int v, int vl, int vr) {
        tree[v].mx = max(tree[v].mx, tree[v].dept);
        if (vr - vl != 1) {
            tree[2 * v].dept = max(tree[2 * v].dept, tree[v].dept);
            tree[2 * v + 1].dept = max(tree[2 * v + 1].dept, tree[v].dept);
        }
        tree[v].dept = -INF;
    }
    void change(int v, int vl, int vr, int l, int r, int x) {
        if (vl >= r || vr <= l) {
            push(v, vl, vr);
            return;
        }
        if (vl >= l && vr <= r) {
            tree[v].dept = max(tree[v].dept, x);
            push(v, vl, vr);
            return;
        }
        push(v, vl, vr);
        int m = (vl + vr) / 2;
        change(2 * v, vl, m, l, r, x);
        change(2 * v + 1, m, vr, l, r, x);
        tree[v].mx = max(tree[2 * v].mx, tree[2 * v + 1].mx);
    }
    int get(int v, int vl, int vr, int l, int r) {
        push(v, vl, vr);
        if (vl >= r || vr <= l) {
            return -INF;
        }
        if (vl >= l && vr <= r) {
            return tree[v].mx;
        }
        int m = (vl + vr) / 2;
        return max(get(2 * v, vl, m, l, r), get(2 * v + 1, m, vr, l, r));
    }
};

vector<vector<pair<int, int>>> op, cl;
vector<int> lf, rf, tx;
vector<bool> ans;

struct fenwick {
    vector<int> s;
    void change(int i, int x) {
        for (; i < s.size(); i += i & -i) {
            s[i] = max(s[i], x);
        }
    }
    int get(int i) {
        int t = -INF;
        for (; i > 0; i -= i & -i) {
            t = max(t, s[i]);
        }
        return t;
    }
};

void calc(int l, int r) {
    if (r - l <= 1) {
        return;
    }
    int m = (l + r) / 2;
    vector<int> cord;
    for (int i = l; i < r; i++) {
        cord.push_back(lf[i]);
    }
    sort(cord.begin(), cord.end());
    cord.resize(unique(cord.begin(), cord.end()) - cord.begin());
    int len = (int)cord.size();
    fenwick t; t.s.resize(len + 1, -INF);
    int idx = (int)cord.size() - 1;
    for (int j = m - 1; j >= l; j--) {
        int id = lower_bound(cord.begin(), cord.end(), lf[j]) - cord.begin();
        t.change(id + 1, rf[j]);
        while (!op[j].empty() && op[j].back().first >= m) {
            while (idx >= 0 && cord[idx] >= j) idx--;
            tx[op[j].back().second] = idx + 1;
            if (t.get(idx + 1) > op[j].back().first) {
                ans[op[j].back().second] = false;
            }
            op[j].pop_back();
        }
    }
    t.s.clear(); t.s.resize(len + 1, -INF);
    for (int j = m; j < r; j++) {
        int id = lower_bound(cord.begin(), cord.end(), lf[j]) - cord.begin();
        t.change(id + 1, rf[j]);
        while (!cl[j].empty() && cl[j].back().first < m) {
            idx = tx[cl[j].back().second];
            if (t.get(idx) > j) {
                ans[cl[j].back().second] = false;
            }
            cl[j].pop_back();
        }
    }
    calc(l, m);
    calc(m, r);
}

void solve() {
    int n; cin >> n;
    vector<int> a(n), cord;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cord.push_back(a[i]);
    }
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        cord.push_back(b[i]);
    }
    sort(cord.begin(), cord.end());
    cord.resize(unique(cord.begin(), cord.end()) - cord.begin());
    int m = (int)cord.size();
    lf.resize(n);
    seg_tree t1, t2;
    t1.tree.resize(4 * m), t2.tree.resize(4 * m);
    for (int i = 0; i < n; i++) {
        int lt = lower_bound(cord.begin(), cord.end(), b[i]) - cord.begin();
        int rt = lower_bound(cord.begin(), cord.end(), a[i]) - cord.begin();
        lf[i] = max(t1.get(1, 0, m, lt, rt + 1), t2.get(1, 0, m, lt, lt + 1));
        t1.change(1, 0, m, lt, lt + 1, i);
        t2.change(1, 0, m, lt, rt + 1, i);
    }
    rf.resize(n);
    t1.tree.clear(), t2.tree.clear();
    t1.tree.resize(4 * m), t2.tree.resize(4 * m);
    for (int i = n - 1; i >= 0; i--) {
        int lt = lower_bound(cord.begin(), cord.end(), b[i]) - cord.begin();
        int rt = lower_bound(cord.begin(), cord.end(), a[i]) - cord.begin();
        rf[i] = -max(t1.get(1, 0, m, lt, rt + 1), t2.get(1, 0, m, lt, lt + 1));
        t1.change(1, 0, m, lt, lt + 1, -i);
        t2.change(1, 0, m, lt, rt + 1, -i);
    }
    op.resize(n), cl.resize(n);
    int q; cin >> q;
    ans.resize(q, true);
    tx.resize(q);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        l--, r--;
        op[l].emplace_back(r, i);
        cl[r].emplace_back(l, i);
    }
    for (int i = 0; i < n; i++) {
        sort(op[i].begin(), op[i].end());
        sort(cl[i].rbegin(), cl[i].rend());
    }
    calc(0, n);
    for (int i = 0; i < q; i++) {
        if (ans[i]) cout << "Yes\n";
        else cout << "No\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...