Submission #1344698

#TimeUsernameProblemLanguageResultExecution timeMemory
1344698kuzma_aCurtains (NOI23_curtains)C++20
45 / 100
1625 ms1100752 KiB
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
//#define int long long

using namespace std;

constexpr int sq = 1000;
vector<vector<int>>mn(501,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++){
        for(int j = i*sq;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 < i*sq){
                        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]<<' ';
    }
    */
    map<pair<int,int>,int>mp;
    vector<pair<int,int>>qr[sq];
    vector<pair<int,int>>qq;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        qq.push_back(make_pair(l,r));
        int b = l/sq;
        if(b*sq == l){
            if(mn[b][r] == b*sq-1){
                mp[make_pair(l,r)] = 1;
            }
            else{
                mp[make_pair(l,r)] = 0;
            }
        }
        else{
            qr[b].push_back(make_pair(r,l));
        }
    }
    //cout<<endl;
    for(int i = 0;i<sq;i++){
        sort(qr[i].begin(),qr[i].end());
        for(int j = qr[i].size()-1;j>=0;j--){
            int l = qr[i][j].second,r = qr[i][j].first;
            int go = r;
            if(r >= (i+1)*sq){
                //cout<<1<<endl;
                go = mn[i+1][r];
            }
            int rr = l-1;
            //cout<<l<<' '<<min(go,(i+1)*sq-1)<<endl;
            for(int j = l;j<=min(go,(i+1)*sq-1);j++){
                while(rt[j].size() && *--rt[j].end() > r){
                    //cout<<"DEL"<<' '<<j<<' '<<*--rt[j].end()<<endl;
                    rt[j].erase(--rt[j].end());
                }
                if(j > rr+1){
                    break;
                }
                else{
                    //cout<<j<<' '<<rt[j].size()<<endl;
                    if(rt[j].size()){
                        rr = max(rr,*--rt[j].end());
                    }
                }
            }
            //cout<<l<<' '<<r<<' '<<rr<<' '<<go<<endl;
            if(rr >= go){
                mp[make_pair(l,r)] = 1;
            }
            else{
                mp[make_pair(l,r)] = 0;
            }
        }
    }
    for(auto it:qq){
        if(mp[it]){
            cout<<"YES";
        }
        else{
            cout<<"NO";
        }
        cout<<"\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...