Submission #1170843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170843		Craftless	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	2595 ms	15060 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];
pair<pi, int> 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];
    }
    for (int i = 1; i <= N; i++) {
        cin >> B[i];
        AA[i] = { { A[i], B[i] }, 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<pair<pi, int>> As(AA + L[q], AA + R[q] + 1);
        sort(As.begin(), As.end(), greater<pair<pi, int>>());
        vector<pair<pi, int>> Cs(C + L[q], C + R[q] + 1);
        sort(Cs.begin(), Cs.end(), greater<pair<pi, int>>());
        int ptr = 0;
        set<pi> s; // sorted in terms of smaller Bs, with idx too
        // deque<int> dq;
        for (int i = 0; i < Cs.size(); i++) {
            auto [ba, idx] = Cs[i];
            auto [b, a] = ba;
            while (ptr < As.size() and As[ptr].F.F >= b) {
                s.insert({ As[ptr].F.S, As[ptr].S });
                // dq.pb(As[ptr].S);
                ptr++;
            } // if neither are urs, then pick the one whose B is lower
            // cout << dq.size() << " ";
            if (s.size()) {
                if (s.begin()->S != idx) s.erase(s.begin());
                else if (s.size() >= 2) s.erase(++s.begin());
                else {
                    cout << "No\n";
                    break;
                }
            }
            else {
                cout << "No\n";
                break;
            }
            // if (dq.size()) {
            //     if (dq.front() != idx and dq.back() != idx) {
            //         if (dq.front())
            //     }
            //     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: 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