Submission #1313105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313105		aryan	Curtains (NOI23_curtains)	C++20	0 / 100	1 ms	332 KiB

curtains

#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((int) ms.size() > 0 && *ms.begin() <= e){
            auto it = ms.upper_bound(e);
            it --;
            best = *it;
        }else{
            continue;
        }
        while(cur < best){
            cur ++;
            for(int &e2 : hs[cur]){
                ms.insert(e2);
            }
            auto it = ms.upper_bound(e);
            it --;
            best = *it;
            if(cur == best && best < e){
                for(int &e2 : hs[cur + 1]){
                    ms.insert(e2);
                }
                auto it = ms.upper_bound(e);
                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;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20