제출 #1182547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182547		asli_bg	Curtains (NOI23_curtains)	C++20	0 / 100	56 ms	106056 KiB

curtains

#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define int long long

typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<bool> vb;

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
#define sp <<" "<<

#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

#define DEBUG(x) cout<<#x sp x<<endl;
#define carp(x,y) ((x%MOD)*(y%MOD))%MOD
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define mid (l+r)/2

const int MAXN=5e5+5;
const int MOD=1e9+7;
const int INF=1e18;

int n,m,q;

vii ar;

vii tut[MAXN];

vii t[4*MAXN];
vii pref[4*MAXN]; //{boşluk,gidebilecek en uzak mesafe}

void merge(vii& c,vii& a, vii& b,int nd,int l,int r){
    int sz1=a.size();
    int sz2=b.size();

    int p1,p2;
    p1=p2=0;

    int bir,iki;
    bir=-1;
    iki=-1;

    vi vec;

    while(p1<sz1 or p2<sz2){
        if(p1>=sz1 or (p2<sz2 and a[p1].fi>b[p2].fi)){
            int deg=ar[b[p2].se].fi;
            if(c.empty()){
                if(deg>l){
                    FORE(i,l,deg){
                        vec.pb(i);
                    }
                }
            } 
            else{
                int once=c.back().fi;
                if(deg>once){
                    FORE(i,once+1,deg){
                        vec.pb(i);
                    }
                }
                else{
                    while(!vec.empty() and vec.back()>=deg) vec.pop_back();
                }
            }

            iki=max(pref[nd*2+1][p2].se,iki);
            if(vec.empty()) bir=-1;
            else bir=vec.back();
            if(iki<r) bir=r;

            c.pb(b[p2++]);
        }
        else{
            int deg=ar[a[p1].se].fi;
            if(c.empty()){
                if(deg>l){
                    FORE(i,l,deg){
                        vec.pb(i);
                    }
                }
            } 
            else{
                int once=c.back().fi;
                if(deg>once){
                    FORE(i,once+1,deg){
                        vec.pb(i);
                    }
                }
                else{
                    while(!vec.empty() and vec.back()>=deg) vec.pop_back();
                }
            }

            iki=max(pref[nd*2][p1].se,iki);
            if(vec.empty()) bir=-1;
            else bir=vec.back();
            if(iki<r) bir=r;

            c.pb(a[p1++]);
        }
        pref[nd].pb({bir,iki});
    }
}

void build(int nd=1,int l=1,int r=n){
    if(l==r){
        int bir,iki;
        bir=l;
        iki=-1;
        for(auto el:tut[l]){
            t[nd].pb(el);
            bir=-1;
            iki=max(iki,el.fi);
            pref[nd].pb({bir,iki});
        }
        return;
    }

    build(nd*2,l,mid);
    build(nd*2+1,mid+1,r);

    merge(t[nd],t[nd*2],t[nd*2+1],nd,l,r);
}

vector<pair<pii,int>> segt;

void query(int ql,int qr,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return;
    
    pii res;
    if(ql<=l and r<=qr){
        segt.pb({{l,r},nd});
        return;
    }
    
    query(ql,qr,nd*2,l,mid);
    query(ql,qr,nd*2+1,mid+1,r);
}

bool mm(pii a,pii b){
    return a.se<b.se;
}

bool solve(int ql,int qr){
    int iki=-1;

    FOR(i,segt.size()){
        int nd=segt[i].se;
        int l=segt[i].fi.fi;
        int r=segt[i].fi.se;

        if(t[nd].empty()){
            if(iki < r) return false;
        }
        else{
            pii pp={qr,INF};
            auto it=upper_bound(all(t[nd]),pp);
            if(it==t[nd].begin()){
                if(iki < r) return false;
            }
            it--;
            int ind=it-t[nd].begin();
            if(pref[nd][ind].fi!=-1 and iki < pref[nd][ind].fi) return false;
            iki=max(iki,pref[nd][ind].se);
        }
    }

    if(iki<qr) return false;
    return true;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m>>q;
    ar.resize(m+1);
    FORE(i,1,m+1){
        cin>>ar[i].fi>>ar[i].se;
    }

    sort(all(ar),mm);

    FORE(i,1,m+1) tut[ar[i].fi].pb({ar[i].se,i});
    
    build();

    while(q--){
        int l,r;
        cin>>l>>r;

        segt.clear();
        query(l,r);

        if(solve(l,r)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}   

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