Submission #1313116

#TimeUsernameProblemLanguageResultExecution timeMemory
1313116aryanCurtains (NOI23_curtains)C++20
20 / 100
422 ms43904 KiB
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


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

    int n,m,q;
    cin >> n >> m >> q;
    vector<int> l(m),r(m);
    vector<vector<int>> hs(n + 5);
    for(int i = 0;i < m;i++){
        cin >> l[i] >> r[i];
        l[i] --;
        r[i] --;
        hs[l[i]].push_back(r[i]);
    }

    vector<pair<int,int>> que;
    for(int i = 0;i < q;i++){
        int s,e;
        cin >> s >> e;
        s --;
        e --;
        assert(s == 0);
        que.push_back({e,i});
    }

    sort(que.begin(),que.end());
    int cur = -1;
    set<int> ms;
    ms.insert(n + 1);
    int best = -1;
    for(int &e : hs[0]) ms.insert(e);
    vector<bool> ans(q,false);

    for(auto p: que){
        int e = p.first;
        if(*ms.begin() <= e){
            auto it = ms.upper_bound(e);
              assert(it != ms.begin());
            it --;
            best = *it;
        }else{
            continue;
        }
        if(cur == best && best < e){
                for(int &e2 : hs[cur + 1]){
                    ms.insert(e2);
                }
                auto it = ms.upper_bound(e);
                assert(it != ms.begin());
                it --;
                best = *it;
        }
        while(cur < best){
            assert(best <= e);
            cur ++;
            for(int &e2 : hs[cur]){
                ms.insert(e2);
            }
            auto it = ms.upper_bound(e);
            assert(it != ms.begin());
            it --;
            best = *it;
            if(cur == best && best < e){
                for(int &e2 : hs[cur + 1]){
                    ms.insert(e2);
                }
                auto it = ms.upper_bound(e);
                assert(it != ms.begin());
                it --;
                best = *it;
            }
        }
        assert(cur <= e);
        if(cur == e){
            ans[p.second] = true;
        }
    }
    for(int i = 0;i < q;i++) cout << (ans[i] ? "YES\n" : "NO\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...