Submission #1313096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313096		aryan	Curtains (NOI23_curtains)	C++20	9 / 100	1595 ms	2396 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]);
    }

    for(int i = 0;i < n;i++){
        sort(hs[i].begin(),hs[i].end());
        hs[i].erase(unique(hs[i].begin(),hs[i].end()),hs[i].end());
    }

    while(q --){
        int s,e;
        cin >> s >> e;
        s --;
        e --;
        int cur = s - 1;
        if((int)hs[s].size() == 0){
            cout << "NO\n";
            continue;
        }
        int best = upper_bound(hs[s].begin(),hs[s].end(),e) - hs[s].begin();
        best --;
        if(best < 0){
            cout << "NO\n";
            continue;
        }
        best = hs[s][best];
        while(cur < best){
                cur ++;
                if((int) hs[cur].size() != 0){
                    int ind = upper_bound(hs[cur].begin(),hs[cur].end(),e) - hs[cur].begin();
                    ind --;
                    if(ind >= 0){
                        best = max(best,hs[cur][ind]);
                        assert(best <= e);
                    }
                }
                if(cur == best && best < e && (int)hs[cur + 1].size() > 0){
                    int ind = upper_bound(hs[cur + 1].begin(),hs[cur + 1].end(),e) - hs[cur + 1].begin();
                    ind --;
                    if(ind >= 0){
                        best = hs[cur + 1][ind];
                    }
                }
            
        }
        assert(cur <= e);
        if(cur == e){
            cout << "YES\n";
        }else{
            cout << "NO\n";
        }
    }

    return 0;
}

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