제출 #1357632

#제출 시각아이디문제언어결과실행 시간메모리
1357632gayGift Exchange (JOI24_ho_t4)C++20
88 / 100
2598 ms239500 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));
    }
};

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

void calc(ll l, ll r) {
    if (r - l <= 1) {
        return;
    }
    ll m = (l + r) / 2;
    vector<ll> cord;
    for (ll i = l; i < r; i++) {
        cord.push_back(lf[i]);
    }
    sort(cord.begin(), cord.end());
    cord.resize(unique(cord.begin(), cord.end()) - cord.begin());
    ll len = (int)cord.size();
    seg_tree t1;
    t1.tree.resize(4 * len);
    for (ll j = m - 1; j >= l; j--) {
        ll id = lower_bound(cord.begin(), cord.end(), lf[j]) - cord.begin();
        t1.change(1, 0, len, id, id + 1, rf[j]);
        while (!op[j].empty() && op[j].back().first >= m) {
            ll idx = lower_bound(cord.begin(), cord.end(), j) - cord.begin();
            if (t1.get(1, 0, len, 0, idx) > op[j].back().first) {
                ans[op[j].back().second] = false;
            }
            op[j].pop_back();
        }
    }
    t1.tree.clear();
    t1.tree.resize(4 * len);
    for (ll j = m; j < r; j++) {
        ll id = lower_bound(cord.begin(), cord.end(), lf[j]) - cord.begin();
        t1.change(1, 0, len, id, id + 1, rf[j]);
        while (!cl[j].empty() && cl[j].back().first < m) {
            ll idx = lower_bound(cord.begin(), cord.end(), cl[j].back().first) - cord.begin();
            if (t1.get(1, 0, len, 0, 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<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();
    lf.resize(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);
    }
    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--) {
        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);
    }
    op.resize(n), cl.resize(n);
    ll q; cin >> q;
    ans.resize(q, true);
    for (int i = 0; i < q; i++) {
        ll 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";
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…