Submission #1170838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170838		Craftless	Gift Exchange (JOI24_ho_t4)	C++20	10 / 100	2594 ms	10112 KiB

Main

#include <bits/stdc++.h>

#define int long long int
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define INF 1e13

using namespace std;

int N, A[500010], B[500010], Q, L[200010], R[200010], T[200010];
pi AA[500010];
pair<pi, int> C[500010];

int32_t main() {

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        AA[i] = { A[i], i };
    }
    for (int i = 1; i <= N; i++) {
        cin >> B[i];
        C[i] = { { B[i], A[i] }, i };
    }
    // sort(C + 1, C + N + 1, greater<pi>());
    // sort(A + 1, A + N + 1, greater<int>());
    // no of ppl before me 
    // no of ppl larger than me
    // larger than me - before me == 1 then too bad
    // sliding window, more available
    // orig, 2 available
    // slide from 
    // 2 - 1
    cin >> Q;
    for (int q = 0; q < Q; q++) {
        cin >> L[q] >> R[q];



        // memset(T, 0, sizeof(T));
        // int taken = 0;
        vector<pi> As(AA + L[q], AA + R[q] + 1);
        sort(As.begin(), As.end(), greater<pi>());
        vector<pair<pi, int>> Cs(C + L[q], C + R[q] + 1);
        sort(Cs.begin(), Cs.end(), greater<pair<pi, int>>());
        int ptr = 0;
        deque<int> dq;
        for (int i = 0; i < Cs.size(); i++) {
            auto [ba, idx] = Cs[i];
            auto [b, a] = ba;
            while (As[ptr].F >= b) {
                dq.pb(As[ptr].S);
                ptr++;
            }
            if (dq.size()) {
                if (dq.front() != idx) {
                    dq.pop_front();
                }
                else if (dq.back() != idx) {
                    dq.pop_back();
                }
                else {
                    cout << "No\n";
                    break;
                }
            }
            else {
                cout << "No\n";
                break;
            }
            if (i == Cs.size() - 1) cout << "Yes\n";
        }

        // for (int j = 0; j < Cs.size(); j++) {
        //     auto [b, a] = Cs[j];
        //     int larger = As.size() - (lower_bound(As.begin(), As.end(), b) - As.begin());
        //     if (larger == 1) {
        //         cout << "No\n";
        //         break;
        //     }
        //     // cout << b << a << "_" << As.size() << " " << larger << " ";
        //     larger -= taken;
        //     if (larger > 1) taken++;
        //     else {
        //         cout << "No\n";
        //         break;
        //     }
        //     if (j == Cs.size() - 1) 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