Submission #1345159

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

using namespace std;

int mv[30][500000],ch[30][500000];

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

    int n,m,qq;
    cin>>n>>m>>qq;
    set<int>rt[n],lft[n];
    set<int>crs;
    for(int i = 0;i<m;i++){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        if(l == r){
            crs.insert(l);
        }
        rt[l].insert(r);
        lft[r].insert(l);
    }
    set<int>qr[n];
    map<pair<int,int>,int>mp;
    vector<pair<int,int>>v1;
    while(qq--){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        v1.push_back(make_pair(l,r));
        if(l < r){
            qr[l].insert(r);
        }
        else if(crs.find(l) != crs.end()){
            mp[make_pair(l,l)] = 1;
        }
    }
    queue<pair<int,pair<int,int>>>q;
    q.push(make_pair(0,make_pair(0,n-1)));
    while(q.size()){
        int l = q.front().second.first,r = q.front().second.second;
        int k = q.front().first;
        q.pop();
        int m = (l+r)/2;
        //cout<<l<<' '<<r<<endl;
        for(int i = m;i>=l;i--){
            mv[k][i] = n+2;
            ch[k][i] = i;
            int rr = i;
            while(rt[i].size() && *--rt[i].end() > m){
                mv[k][i] = *--rt[i].end();
                rt[i].erase(--rt[i].end());
            }
            int go = i-1;
            if(rt[i].size()){
                go = *--rt[i].end();
            }
            while(rr <= go+1){
                if(rr > r){
                    break;
                }
                mv[k][i] = min(mv[k][i],mv[k][rr]);
                rr = max(rr,ch[k][rr]);
                if(rr <= go){
                    rr++;
                }
                else{
                    if(rr > r || ch[k][rr] <= rr){
                        if(rr <= r){
                            mv[k][i] = min(mv[k][i],mv[k][rr]);
                        }
                        break;
                    }
                }
            }
            ch[k][i] = rr;
        }
        for(int i = m+1;i<=r;i++){
            mv[k][i] = -2;
            ch[k][i] = i;
            int ll = i;
            while(lft[i].size() && *lft[i].begin() <= m){
                mv[k][i] = *lft[i].begin();
                lft[i].erase(lft[i].begin());
            }
            int go = i+1;
            if(lft[i].size()){
                go = *lft[i].begin();
            }
            while(ll >= go-1){
                if(ll < l){
                    break;
                }
                mv[k][i] = max(mv[k][i],mv[k][ll]);
                ll = min(ll,ch[k][ll]);
                if(ll >= go){
                    ll--;
                }
                else{
                    if(ll < l || ch[k][ll] >= ll){
                        if(ll >= l){
                            mv[k][i] = max(mv[k][i],mv[k][ll]);
                        }
                        break;
                    }
                }
            }
            ch[k][i] = ll;
        }
        for(int i = l;i<=m;i++){
            while(qr[i].size() && *--qr[i].end() > m){
                int r = *--qr[i].end();
                if(mv[k][r] >= i && mv[k][i] <= r){
                    mp[make_pair(i,r)] = 1;
                }
                //cout<<i<<' '<<r<<' '<<mp[make_pair(i,r)]<<endl;
                qr[i].erase(--qr[i].end());
            }
        }
        /*
        for(int i = 0;i<n;i++){
            cout<<mv[i]<<' ';
        }
        cout<<endl;
        for(int i = 0;i<n;i++){
            cout<<ch[i]<<' ';
        }
        cout<<endl;
        */
        if(m > l){
            q.push(make_pair(k+1,make_pair(l,m)));
        }
        if(m+1 < r){
            q.push(make_pair(k+1,make_pair(m+1,r)));
        }
    }
    for(auto it:v1){
        if(mp[it]){
            cout<<"YES";
        }
        else{
            cout<<"NO";
        }
        cout<<endl;
    }
}
#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...