제출 #1345208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1345208		kuzma_a	Curtains (NOI23_curtains)	C++20	45 / 100	1537 ms	150844 KiB

curtains

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

using namespace std;

int mv[500000],ch[500000];
set<int>rt[500000],lft[500000];
map<pair<int,int>,int>mp;
set<int>qr[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>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);
    }
    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;
        for(int i = m;i>=l;i--){
            mv[i] = n+2;
            ch[i] = i;
            int rr = i;
            while(rt[i].size() && *--rt[i].end() > m){
                mv[i] = *--rt[i].end();
                rt[i].erase(--rt[i].end());
            }
            int go = i-1;
            if(rt[i].size()){
                go = *--rt[i].end();
            }
            if(go != m){
                while(rr <= go+1){
                    if(rr > m){
                        break;
                    }
                    mv[i] = min(mv[i],mv[rr]);
                    rr = max(rr,ch[rr]);
                    if(rr <= go){
                        rr++;
                    }
                    else{
                        if(rr > m || ch[rr] <= rr){
                            if(rr <= m){
                                mv[i] = min(mv[i],mv[rr]);
                            }
                            break;
                        }
                    }
                }
                ch[i] = rr-1;
            }
            else{
                mv[i] = m;
                ch[i] = m;
            }
        }
        for(int i = m+1;i<=r;i++){
            mv[i] = -2;
            ch[i] = i;
            int ll = i;
            while(lft[i].size() && *lft[i].begin() <= m){
                mv[i] = *lft[i].begin();
                lft[i].erase(lft[i].begin());
            }
            int go = i+1;
            if(lft[i].size()){
                go = *lft[i].begin();
            }
            if(go != m+1){
                while(ll >= go-1){
                    if(ll <= m){
                        break;
                    }
                    mv[i] = max(mv[i],mv[ll]);
                    ll = min(ll,ch[ll]);
                    if(ll >= go){
                        ll--;
                    }
                    else{
                        if(ll <= m || ch[ll] >= ll){
                            if(ll > m){
                                mv[i] = max(mv[i],mv[ll]);
                            }
                            break;
                        }
                    }
                }
                ch[i] = ll+1;
            }
            else{
                mv[i] = m+1;
                ch[i] = m+1;
            }
        }
        for(int i = l;i<=m;i++){
            while(qr[i].size() && *--qr[i].end() > m){
                int r = *--qr[i].end();
                if(mv[r] >= i && mv[i] <= r){
                    mp[make_pair(i,r)] = 1;
                }
                qr[i].erase(--qr[i].end());
            }
        }
        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<<"\n";
    }
}

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