Submission #1041140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041140		victor_gao	Gift Exchange (JOI24_ho_t4)	C++17	100 / 100	1717 ms	140192 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define N 500015
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, q, L1[N], R1[N], L2[N], R2[N], L[N], R[N], ord[2 * N], ans[N];
pii arr[N];
vector<int> qry[2 * N], rem[N];
vector<pii> query[N];

void solve(int l, int r){
    int mid = (l + r) >> 1;
    set<int> A;
    for (int i = l; i <= mid; i++)
        if (ord[i] > n && arr[ord[i] - n].x - 1 > mid)
            qry[min(r, arr[ord[i] - n].x - 1)].emplace_back(ord[i] - n);
    for (int i = mid + 1; i <= r; i++){ // B match A
        if (ord[i] <= n)
            A.insert(ord[i]);
        for (auto j : qry[i]){
            if (A.empty())
                continue;
            auto it = A.upper_bound(j);
            if (it != A.end())
                R1[j] = min(R1[j], *it);
            if (it != A.begin())
                L1[j] = max(L1[j], *prev(it));
        }
        qry[i].clear();
    }
}

void merge(int l, int r){
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    merge(l, mid), merge(mid + 1, r);
    solve(l, r);
}

struct segtree{
    int seg[4 * N];
    void modify(int l, int r, int i, int p, int c){
        if (l == r){
            seg[i] = c;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) modify(l, mid, i << 1, p, c);
        else modify(mid + 1, r, i << 1 | 1, p, c);
        seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
    }
    int query(int l, int r, int i, int ll, int rr){
        if (ll <= l && rr >= r)
            return seg[i];
        int mid = (l + r) >> 1;
        if (rr <= mid) return query(l, mid, i << 1, ll, rr);
        else if (ll > mid) return query(mid + 1, r, i << 1 | 1, ll, rr);
        else return min(query(l, mid, i << 1, ll, rr), query(mid + 1, r, i << 1 | 1, ll, rr));
    }
}seg;


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i].x, ord[arr[i].x] = i;
    for (int i = 1; i <= n; i++)
        cin >> arr[i].y, ord[arr[i].y] = i + n;
    fill(R1, R1 + N, n + 1);
    fill(R2, R2 + N, n + 1);
    merge(1, 2 * n);
    set<int> B;
    for (int i = 1; i <= 2 * n; i++){
        if (ord[i] <= n){
            B.erase(ord[i]);
            if (B.empty())
                continue;
            auto it = B.upper_bound(ord[i]);
            if (it != B.end())
                R2[ord[i]] = min(R2[ord[i]], *it);
            if (it != B.begin())
                L2[ord[i]] = max(L2[ord[i]], *prev(it));
        }
        else B.insert(ord[i] - n);
    }

    cin >> q;
    for (int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        query[r].emplace_back(l, i);
    }
    
    for (int i = 1; i <= n; i++){
        L[i] = max(L1[i], L2[i]);
        R[i] = min(R1[i], R2[i]);
        rem[R[i]].emplace_back(i);
    }

    for (int i = 1; i <= n; i++){
        seg.modify(1, n, 1, i, L[i]);
        for (auto id : rem[i])
            seg.modify(1, n, 1, id, n + 1);
        for (auto [l, id] : query[i])
            ans[id] = (seg.query(1, n, 1, l, i) >= l) ? 1 : 0;
    }
    for (int i = 1; i <= q; i++)
        cout << ((ans[i] == 1) ? "Yes\n" : "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