Submission #1308759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308759		orzorzorz	Gift Exchange (JOI24_ho_t4)	C++20	10 / 100	27 ms	26628 KiB

Main

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

using namespace std;

const int MAXN = 500005;
const int LOGN = 20;

int N, Q;
int A[MAXN];
int B[MAXN];
int lg2[MAXN];

// ST表定义
// st_max_b_idx[k][i]: 存储区间 [i, i + 2^k - 1] 中 B 值最大的下标
// st_min_b_idx[k][i]: 存储区间 [i, i + 2^k - 1] 中 B 值最小的下标
// st_max_a_val[k][i]: 存储区间 [i, i + 2^k - 1] 中 A 的最大值
// st_min_b_val[k][i]: 存储区间 [i, i + 2^k - 1] 中 B 的最小值 (用于找第二小)

int st_max_b_idx[LOGN][MAXN];
int st_min_b_idx[LOGN][MAXN];
int st_max_a_val[LOGN][MAXN];
int st_min_b_val[LOGN][MAXN];

void build_st() {
    lg2[1] = 0;
    for (int i = 2; i <= N; i++) lg2[i] = lg2[i / 2] + 1;

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

    for (int j = 1; j < LOGN; j++) {
        for (int i = 1; i + (1 << j) - 1 <= N; i++) {
            // Max B Index
            int idx1 = st_max_b_idx[j - 1][i];
            int idx2 = st_max_b_idx[j - 1][i + (1 << (j - 1))];
            if (B[idx1] >= B[idx2]) st_max_b_idx[j][i] = idx1;
            else st_max_b_idx[j][i] = idx2;

            // Min B Index
            idx1 = st_min_b_idx[j - 1][i];
            idx2 = st_min_b_idx[j - 1][i + (1 << (j - 1))];
            if (B[idx1] <= B[idx2]) st_min_b_idx[j][i] = idx1;
            else st_min_b_idx[j][i] = idx2;

            // Max A Value
            st_max_a_val[j][i] = max(st_max_a_val[j - 1][i], st_max_a_val[j - 1][i + (1 << (j - 1))]);
            
            // Min B Value
            st_min_b_val[j][i] = min(st_min_b_val[j - 1][i], st_min_b_val[j - 1][i + (1 << (j - 1))]);
        }
    }
}

// 查询区间 [L, R] 中 B 最大值的下标
int query_max_b_idx(int L, int R) {
    int k = lg2[R - L + 1];
    int idx1 = st_max_b_idx[k][L];
    int idx2 = st_max_b_idx[k][R - (1 << k) + 1];
    return (B[idx1] >= B[idx2]) ? idx1 : idx2;
}

// 查询区间 [L, R] 中 B 最小值的下标
int query_min_b_idx(int L, int R) {
    int k = lg2[R - L + 1];
    int idx1 = st_min_b_idx[k][L];
    int idx2 = st_min_b_idx[k][R - (1 << k) + 1];
    return (B[idx1] <= B[idx2]) ? idx1 : idx2;
}

// 查询区间 [L, R] 中 A 的最大值，如果区间不合法返回 -1
int query_max_a_val(int L, int R) {
    if (L > R) return -1;
    int k = lg2[R - L + 1];
    return max(st_max_a_val[k][L], st_max_a_val[k][R - (1 << k) + 1]);
}

// 查询区间 [L, R] 中 B 的最小值，如果区间不合法返回 INF
int query_min_b_val(int L, int R) {
    if (L > R) return 2e9; // Infinity
    int k = lg2[R - L + 1];
    return min(st_min_b_val[k][L], st_min_b_val[k][R - (1 << k) + 1]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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. 检查接收瓶颈：Max B 是否能被其他人满足
        int idx_max_b = query_max_b_idx(L, R);
        int max_b_val = B[idx_max_b];
        
        // 在 [L, R] 中除了 idx_max_b 以外找最大的 A
        int max_a_left = query_max_a_val(L, idx_max_b - 1);
        int max_a_right = query_max_a_val(idx_max_b + 1, R);
        int max_a_others = max(max_a_left, max_a_right);

        if (max_a_others < max_b_val) {
            cout << "No\n";
            continue;
        }

        // 2. 检查发送瓶颈：Min B 是否能送给第二小 B 的人
        int idx_min_b = query_min_b_idx(L, R);
        int a_source = A[idx_min_b];
        
        // 在 [L, R] 中除了 idx_min_b 以外找最小的 B (即第二小 B)
        int min_b_left = query_min_b_val(L, idx_min_b - 1);
        int min_b_right = query_min_b_val(idx_min_b + 1, R);
        int second_min_b = min(min_b_left, min_b_right);

        if (a_source < second_min_b) {
            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