Submission #1357631

#TimeUsernameProblemLanguageResultExecution timeMemory
1357631gayGift Exchange (JOI24_ho_t4)C++20
58 / 100
2594 ms30996 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 ll INF = 3e18, 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 {
        ll mx = -INF, dept = -INF;
    };
    vector<Node> tree;
    void push(ll v, ll vl, ll 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(ll v, ll vl, ll vr, ll l, ll r, ll 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);
        ll 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);
    }
    ll get(ll v, ll vl, ll vr, ll l, ll r) {
        push(v, vl, vr);
        if (vl >= r || vr <= l) {
            return -INF;
        }
        if (vl >= l && vr <= r) {
            return tree[v].mx;
        }
        ll m = (vl + vr) / 2;
        return max(get(2 * v, vl, m, l, r), get(2 * v + 1, m, vr, l, r));
    }
};

void solve() {
    int n; cin >> n;
    vector<ll> a(n), cord;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cord.push_back(a[i]);
    }
    vector<ll> 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());
    ll m = (int)cord.size();
    vector<ll> lf(n);
    seg_tree t1, t2;
    t1.tree.resize(4 * m), t2.tree.resize(4 * m);
    for (int i = 0; i < n; i++) {
        ll lt = lower_bound(cord.begin(), cord.end(), b[i]) - cord.begin();
        ll 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);
    }
    vector<ll> rf(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--) {
        ll lt = lower_bound(cord.begin(), cord.end(), b[i]) - cord.begin();
        ll 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);
    }
    ll q; cin >> q;
    while (q--) {
        ll l, r; cin >> l >> r;
        l--, r--;
        bool flag = true;
        for (ll i = l; i <= r; i++) {
            if (lf[i] < l && rf[i] > r) {
                flag = false;
                break;
            }
        }
        if (flag) {
            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...