제출 #1182350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182350		asli_bg	Curtains (NOI23_curtains)	C++20	0 / 100	48 ms	106124 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)){
            while(!vec.empty() and vec.back()>=ar[b[p2].se].fi) vec.pop_back();

            if(!c.empty()){
                if(c.back().fi+1<ar[b[p2].se].fi){
                    vec.pb(ar[b[p2].se].fi-1);
                }
            }
            else{
                if(ar[b[p2].se].fi>l){
                    vec.pb(ar[b[p2].se].fi-1);
                }
            }

            iki=max(pref[nd*2+1][p2].se,iki);
            if(iki<r){
                vec.pb(r);
            }

            if(!vec.empty()) bir=vec.back();
            else bir=-1;

            c.pb(b[p2++]);
        }
        else{
            while(!vec.empty() and vec.back()>=ar[a[p1].se].fi) vec.pop_back();
            
            iki=max(pref[nd*2][p1].se,iki);
            if(iki<r){
                vec.pb(r);
            }

            if(!vec.empty()) bir=vec.back();
            else bir=-1;

            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);
}

pii query(int ql,int qr,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return {-1,-1};
    
    pii res;
    if(ql<=l and r<=qr){
        if(t[nd].empty()) res={r,-1};
        else{
            pii pp={qr,INF};
            auto it=upper_bound(all(t[nd]),pp);
            if(it==t[nd].begin()) res={r,-1};
            else{
                it--;
                res=pref[nd][it-t[nd].begin()];
            }
        }

        return res;
    }
    
    if(qr<=mid) return query(ql,qr,nd*2,l,mid);
    else if(ql>mid) return query(ql,qr,nd*2+1,mid+1,r);
    else{
        auto s1=query(ql,qr,nd*2,l,mid);
        auto s2=query(ql,qr,nd*2+1,mid+1,r);

        pii res;

        if(s1.fi!=-1) res.fi=s1.fi;
        else if(s2.fi!=-1){
            if(s1.se>=s2.fi) res.fi=-1;
            else res.fi=s2.fi;
        }
        else res.fi=-1;

        res.se=max(s1.se,s2.se);

        return res;
    }
}

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

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;

        auto ans=query(l,r);

        if(ans.fi==-1) 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