Submission #1170824

#TimeUsernameProblemLanguageResultExecution timeMemory
1170824CraftlessGift Exchange (JOI24_ho_t4)C++20
10 / 100
28 ms7496 KiB
#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 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];
        C[i] = { B[i], A[i] };
    }
    // sort(C + 1, C + N + 1, greater<pi>());
    // sort(A + 1, A + N + 1, greater<int>());
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> L[i] >> R[i];
        memset(T, 0, sizeof(T));
        int taken = 0;
        vector<int> As(A + L[i], A + R[i] + 1);
        sort(As.begin(), As.end());
        vector<pi> Cs(C + L[i], C + R[i] + 1);
        sort(Cs.begin(), Cs.end(), greater<pi>());
        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 > 0) taken++;
            else {
                cout << "No\n";
                break;
            }
            if (j == Cs.size() - 1) cout << "Yes\n";
        }
    }

    return 0;    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...