Submission #1313125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313125		aryan	Curtains (NOI23_curtains)	C++20	24 / 100	1595 ms	17692 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);
    vector<vector<int>> hsq(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());
        for(int e : hs[i]){
            hsq[i].push_back(e);
        }
    }

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

    sort(que.begin(),que.end(),greater<pair<int,int>>());

    vector<bool> ans(q,false);
    for(auto p : que){
        int e = p.first;
        int ind = p.second;
        int s = sq[ind];

        int cur = s - 1;
        int best = -1;
        while(!hsq[s].empty() && hsq[s].back() > e) hsq[s].pop_back();
        if(!hsq[s].empty()){
            best = hsq[s].back();
        }else{
            continue;
        }
        while(cur < best){
            cur ++;
            while(!hsq[cur].empty() && hsq[cur].back() > e){
                hsq[cur].pop_back();
            }
            if(!hsq[cur].empty()){
                best = max(best,hsq[cur].back());
            }
            if(cur == best && best < e){

                while(!hsq[cur + 1].empty() && hsq[cur + 1].back() > e){
                    hsq[cur + 1].pop_back();
                }
                if(!hsq[cur + 1].empty()){
                    best = max(best,hsq[cur + 1].back());
                }
            }
        }
        if(cur == e){
            ans[ind] = true;
        }
    }
    for(int i = 0;i < q;i++) cout << (ans[i] ? "YES\n" : "NO\n");

    return 0;
}

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