Submission #1308758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308758		orzorzorz	Gift Exchange (JOI24_ho_t4)	C++20	10 / 100	62 ms	32864 KiB

Main

/**
 * JOI 2022 Spring Camp - Present Exchange
 * Solution using Sparse Table + Hall's Marriage Theorem Deduction
 * Time Complexity: O(N log N) build, O(1) per query
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

// 数据规模定义
const int MAXN = 500005;
const int LOGN = 20; // 2^19 > 500,000

int N, Q;
int A[MAXN], B[MAXN];
int lg[MAXN]; // 预处理 log2 值

// 定义 ST 表
// st_max_b_idx: 区间 B 值最大的下标
// st_min_b_idx: 区间 B 值最小的下标
// st_max_a_val: 区间 A 值的最大值
// st_min_b_val: 区间 B 值的最小值 (用于找第二小 B)
int st_max_b_idx[MAXN][LOGN];
int st_min_b_idx[MAXN][LOGN];
int st_max_a_val[MAXN][LOGN];
int st_min_b_val[MAXN][LOGN];

// 辅助函数：比较两个下标对应的 B 值
int get_max_b_idx(int i, int j) {
    return (B[i] > B[j]) ? i : j;
}

int get_min_b_idx(int i, int j) {
    return (B[i] < B[j]) ? i : j;
}

// 构建 ST 表
void build_st() {
    lg[1] = 0;
    for (int i = 2; i <= N; i++)
        lg[i] = lg[i / 2] + 1;

    for (int i = 1; i <= N; i++) {
        st_max_b_idx[i][0] = i;
        st_min_b_idx[i][0] = i;
        st_max_a_val[i][0] = A[i];
        st_min_b_val[i][0] = B[i];
    }

    for (int j = 1; j < LOGN; j++) {
        for (int i = 1; i + (1 << j) - 1 <= N; i++) {
            int right = i + (1 << (j - 1));
            
            // 维护下标
            st_max_b_idx[i][j] = get_max_b_idx(st_max_b_idx[i][j - 1], st_max_b_idx[right][j - 1]);
            st_min_b_idx[i][j] = get_min_b_idx(st_min_b_idx[i][j - 1], st_min_b_idx[right][j - 1]);
            
            // 维护值
            st_max_a_val[i][j] = max(st_max_a_val[i][j - 1], st_max_a_val[right][j - 1]);
            st_min_b_val[i][j] = min(st_min_b_val[i][j - 1], st_min_b_val[right][j - 1]);
        }
    }
}

// 查询函数
int query_max_b_idx(int L, int R) {
    int k = lg[R - L + 1];
    return get_max_b_idx(st_max_b_idx[L][k], st_max_b_idx[R - (1 << k) + 1][k]);
}

int query_min_b_idx(int L, int R) {
    int k = lg[R - L + 1];
    return get_min_b_idx(st_min_b_idx[L][k], st_min_b_idx[R - (1 << k) + 1][k]);
}

int query_max_a_val(int L, int R) {
    if (L > R) return -1; // 空区间返回极小值
    int k = lg[R - L + 1];
    return max(st_max_a_val[L][k], st_max_a_val[R - (1 << k) + 1][k]);
}

int query_min_b_val(int L, int R) {
    if (L > R) return 2e9; // 空区间返回极大值
    int k = lg[R - L + 1];
    return min(st_min_b_val[L][k], st_min_b_val[R - (1 << k) + 1][k]);
}

int main() {
    // 快速 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> N)) return 0;

    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];

    build_st();

    cin >> Q;
    while (Q--) {
        int L, R;
        cin >> L >> R;

        // --- 检查条件 1: 收礼瓶颈 ---
        // 找到区间内需求(B)最大的学生
        int idx_max_b = query_max_b_idx(L, R);
        int val_max_b = B[idx_max_b];
        
        // 查找除了该学生以外，最大的礼物价值(A)
        // 即查询 [L, idx-1] 和 [idx+1, R] 两个区间的最大 A
        int max_a_others = max(query_max_a_val(L, idx_max_b - 1), query_max_a_val(idx_max_b + 1, R));

        // 如果其他人最大的 A 都不足以满足最大的 B，则不可行
        if (max_a_others < val_max_b) {
            cout << "No\n";
            continue;
        }

        // --- 检查条件 2: 送礼瓶颈 ---
        // 找到区间内需求(B)最小的学生 (这是最容易满足的人，但通常他的A较小，容易送不出去)
        int idx_min_b = query_min_b_idx(L, R);
        int val_a_source = A[idx_min_b]; // 这个人持有的礼物价值
        
        // 查找除了该学生以外，最小的需求(B)，即第二小 B
        int min_b_others = min(query_min_b_val(L, idx_min_b - 1), query_min_b_val(idx_min_b + 1, R));
        
        // 如果这个人的 A 连第二小的 B 都满足不了，那他只能满足自己(被禁止)，所以送不出去
        if (val_a_source < min_b_others) {
            cout << "No\n";
            continue;
        }

        cout << "Yes\n";
    }

    return 0;
}

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