제출 #1313123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313123		aryan	Curtains (NOI23_curtains)	C++20	9 / 100	1597 ms	74580 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<stack<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(e);
        }
    }

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

    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].top() > e) hsq[s].pop();
        if(!hsq[s].empty()){
            best = hsq[s].top();
        }else{
            continue;
        }
        while(cur < best){
            cur ++;
            while(!hsq[cur].empty() && hsq[cur].top() > e){
                hsq[cur].pop();
            }
            if(!hsq[cur].empty()){
                best = max(best,hsq[cur].top());
            }
            if(cur == best && best < e){

                while(!hsq[cur + 1].empty() && hsq[cur + 1].top() > e){
                    hsq[cur + 1].pop();
                }
                if(!hsq[cur + 1].empty()){
                    best = max(best,hsq[cur + 1].top());
                }
            }
        }
        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: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20