제출 #1344700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1344700		kuzma_a	Curtains (NOI23_curtains)	C++20	60 / 100	897 ms	218748 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 = 317;
vector<vector<int>>mn(sq,vector<int>(100000,100000));

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

    int n,m,q;
    cin>>n>>m>>q;
    if(n <= 2000){
        int sq = sqrt(n)+1;
        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";
        }
    }
    else if(n <= 100000 && q <= 100000 && m <= 100000){
        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";
        }
    }
    else{
        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: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 0 / 20
• Subtask 5: 36 / 36
• Subtask 6: 0 / 20