Submission #1344687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344687		kuzma_a	Curtains (NOI23_curtains)	C++20	20 / 100	596 ms	98020 KiB

curtains

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
//#define int long long

using namespace std;

constexpr int sq = 1;
vector<vector<int>>mn(sq,vector<int>(500000,500000));

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m,q;
    cin>>n>>m>>q;
    set<int>rt[n],lft[n];
    for(int i = 0;i<m;i++){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        rt[l].insert(r);
        lft[r].insert(l);
    }
    //for(int i = 0;i<sq;i++){
    int i = 0;
        for(int j = 0;j<n;j++){
            mn[i][j] = j;
            while(lft[j].size() && *lft[j].begin() < i*sq){
                lft[j].erase(lft[j].begin());
            }
            if(lft[j].size()){
                int ps = j;
                while(ps >= *lft[j].begin()-1){
                    if(ps < 0){
                        break;
                    }
                    ps = min(ps,mn[i][ps]);
                    if(ps >= *lft[j].begin()){
                        ps--;
                    }
                    else{
                        if(ps <= mn[i][ps]){
                            break;
                        }
                    }
                }
                mn[i][j] = ps;
            }
        }
    //}
    /*
    for(int i = 0;i<n;i++){
        cout<<mn[0][i]<<' ';
    }
    */
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        if(mn[0][r] == -1){
            cout<<"YES";
        }
        else{
            cout<<"NO";
        }
        cout<<endl;
    }
}

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