Submission #1205329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205329		biank	Curtains (NOI23_curtains)	C++20	0 / 100	4 ms	8520 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;

const int SZ=1<<19;
const int INF=1e9+9;

int st[2*SZ],lazy[2*SZ];

void pass(int u){
    if(u<SZ){
        lazy[2*u]=min(lazy[2*u],lazy[u]);
        lazy[2*u+1]=min(lazy[2*u+1],lazy[u]);
    }
    st[u]=min(st[u],lazy[u]);
    lazy[u]=INF;
}

int query_and_upd(int s, int e, int v=INF, int l=0, int r=SZ, int u=1){
    pass(u);
    if(e<=l||r<=s) return 0;
    if(s<=l&&r<=e){
        lazy[u]=v;
        pass(u);
        return st[u];
    }
    int m=(l+r)/2;
    int l_res=query_and_upd(s,e,v,l,m,2*u);
    int r_res=query_and_upd(s,e,v,m,r,2*u+1);
    st[u]=max(st[2*u],st[2*u]+1);
    return max(l_res,r_res);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n,m,q;
    cin>>n>>m>>q;
    vector<vi> ranges(n);
    forn(i,m){
        int l,r;
        cin>>l>>r;
        --l;
        ranges[l].pb(r);
    }
    forn(u,2*SZ) st[u]=lazy[u]=INF;
    vector<vector<ii>> queries(n);
    forn(i,q){
        int l,r;
        cin>>l>>r;
        --l;
        queries[l].eb(r,i);
    }
    vector<bool> res(q);
    dforn(l,n){
        for(int r:ranges[l]){
            query_and_upd(l,r,r);
        }
        for(auto[r,id]:queries[l]){
            res[id]=query_and_upd(l,r)<=r;
        }
    }
    forn(i,q) cout<<(res[i]?"YES\n":"NO\n");
    
    return 0;
}

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