Submission #1245504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245504		RecursiveCo	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	247 ms	28360 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define in(i) cin >> i
#define out(o) cout << o

// vector<int>

vector<int> tree;

void upd(int v, int l, int r, int i, int x) {
    if (l == r) {
        tree[v] = x;
    } else {
        int middle = (l + r) / 2;
        if (i <= middle) upd(2 * v, l, middle, i, x);
        else upd(2 * v + 1, middle + 1, r, i, x);
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }
}

int query(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[v];
    if (qr < l || r < ql) return -1e9;
    int middle = (l + r) / 2;
    int left = query(2 * v, l, middle, ql, qr);
    int right = query(2 * v + 1, middle + 1, r, ql, qr);
    return max(left, right);
}

int base;
int f(int r, int l, int i) {
    return r * base * base + l * base + i;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N;
    in(N);
    vector<int> A(N);
    vector<int> B(N);
    for (int i = 0; i < N; ++i) in(A[i]);
    for (int i = 0; i < N; ++i) in(B[i]);
    for (int i = 0; i < N; ++i) --A[i];
    for (int i = 0; i < N; ++i) --B[i];
    // step 1a: compute L_i and R_i for the case A_i in [B_j, A_j].
    vector<int> at_A(2 * N, -1);
    vector<int> at_B(2 * N, -1);
    for (int i = 0; i < N; ++i) {
        at_A[A[i]] = at_B[B[i]] = i;
    }
    vector<int> L(N, -1);
    vector<int> R(N, 1e9);
    set<int> open;
    for (int i = 0; i < 2 * N; ++i) {
        if (at_B[i] != -1) {
            open.insert(at_B[i]);
        } else if (at_A[i] != -1) {
            int j = at_A[i];
            open.erase(j);
            auto it = open.lower_bound(j);
            if (it != open.end()) R[j] = *it;
            if (it != open.begin()) {
                --it;
                L[j] = *it;
            }
        }
    }
    // step 1b: compute L_i and R_i for the case A_j in [B_i, A_i].
    tree.resize(8 * N, -1);
    for (int i = 0; i < N; ++i) {
        L[i] = max(L[i], query(1, 0, 2 * N - 1, B[i], A[i]));
        upd(1, 0, 2 * N - 1, A[i], i);
    }
    tree.clear();
    tree.resize(8 * N, -1e9);
    for (int i = N - 1; i >= 0; --i) {
        R[i] = min(R[i], -query(1, 0, 2 * N - 1, B[i], A[i]));
        upd(1, 0, 2 * N - 1, A[i], -i);
    }
    vector<array<int, 3>> segs;
    for (int i = 0; i < N; ++i) segs.push_back({R[i], L[i], i});
    sort(segs.begin(), segs.end());
    // step 2: process queries
    int Q;
    in(Q);
    vector<array<int, 3>> queries;
    for (int i = 0; i < Q; ++i) {
        int l, r;
        in(l);
        in(r);
        --l;
        --r;
        queries.push_back({r, l, i});
    }
    sort(queries.begin(), queries.end());
    vector<bool> ans(Q, true);
    int ptr = 0;
    tree.clear();
    tree.resize(4 * N, -1);
    vector<vector<pair<int, int>>> by_l(N);
    base = N + Q;
    for (int i = 0; i < N; ++i) {
        int l = segs[i][1];
        int r = segs[i][0];
        int j = segs[i][2];
        while (ptr < Q && queries[ptr][0] < r) {
            int lh = queries[ptr][1];
            int rh = queries[ptr][0];
            int ind = queries[ptr][2];
            by_l[lh].push_back({rh, ind});
            upd(1, 0, N - 1, lh, f(rh, lh, ind));
            ++ptr;
        }
        while (1) {
            int mx = query(1, 0, N - 1, l + 1, j);
            if (mx == -1) break;
            int rh = mx / (base * base);
            int lh = (mx - rh * base * base) / base;
            int ind = mx % base;
            if (rh < j) break;
            ans[ind] = false;
            by_l[lh].pop_back();
            if (by_l[lh].empty()) upd(1, 0, N - 1, lh, -1e9);
            else upd(1, 0, N - 1, lh, f(by_l[lh].back().first, lh, by_l[lh].back().second));
        }
    }
    for (int i = 0; i < Q; ++i) {
        if (ans[i]) out("Yes");
        else out("No");
        out("\n");
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12