Submission #1136785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136785		Unforgettablepl	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	2594 ms	11368 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> A(n+1),B(n+1);
    for(int i=1;i<=n;i++)cin>>A[i];
    for(int i=1;i<=n;i++)cin>>B[i];
    int q;
    cin >> q;
    for(int i=1;i<=q;i++) {
        int l,r;cin>>l>>r;
        vector<pair<int,int>> gifts;
        set<pair<int,int>> recip;
        for(int j=l;j<=r;j++) {
            gifts.emplace_back(A[j],j);
            recip.insert({B[j],j});
        }
        sort(gifts.begin(), gifts.end());
        bool works = true;
        for(int j=0;j<gifts.size();j++) {
            auto [A,x] = gifts[j];
            auto iter = recip.upper_bound({A,n+1});
            if(iter==recip.begin()) {
                works=false;
                break;
            }
            iter--;
            if(iter->second!=x or (j and gifts[j-1].first>=iter->first)) {
                recip.erase(iter);
                continue;
            }
            if(iter==recip.begin()) {
                works=false;
                break;
            }
            iter--;
            recip.erase(iter);
        }
        if(works)cout<<"Yes\n";
        else cout<<"No\n";
    }
}

• 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