Submission #1331357

#TimeUsernameProblemLanguageResultExecution timeMemory
1331357siquy3001Curtains (NOI23_curtains)C++20
0 / 100
39 ms86516 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,q,l,r;
ll res[500005];
vector<vector<ll>>v(500005,vector<ll>());
vector<vector<pair<ll,ll>>>query(500005,vector<pair<ll,ll>>());
struct node{
    ll val,lazy;
};
node st[4000010];
void down(ll id){
    ll u=st[id].lazy;
    if(u!=0){
        st[2*id].lazy=max(st[2*id].lazy,u);
        st[2*id+1].lazy=max(st[2*id+1].lazy,u);
        st[2*id].val=max(st[2*id].val,u);
        st[2*id+1].val=max(st[2*id+1].val,u);
        st[id].lazy=0;
    }
}
void update(ll id,ll l,ll r,ll u,ll v,ll x){
    if (r<u || v<l)return;
    if (u<=l && r<=v){
        st[id].val=max(st[id].val,x);
        st[id].lazy=max(st[id].lazy,x);
        return;
    }
    down(id);
    ll mid=(l+r)/2;
    update(id*2,l,mid,u,v,x);
    update(id*2+1,mid+1,r,u,v,x);
    st[id].val=min(st[id*2].val,st[id*2+1].val);
}
ll get(ll id,ll l,ll r,ll u,ll v){
    if (r<u || v<l)return 1e18;
    if(u<=l && r<=v)return st[id].val;
    down(id);
    ll mid=(l+r)/2;
    return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        r++;
        v[r].push_back(l);
    }
    for(int i=1;i<=4000005;i++)st[i].val=1;
    for(int i=1;i<=q;i++){
        cin>>l>>r;
        r++;
        query[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++)sort(v[i].begin(),v[i].end());
    for(int i=1;i<=n+1;i++){
        update(1,1,n+1,i,i,i);
        for(auto x:v[i]){
            update(1,1,n+1,x,i,x);
            if(x!=i-1)update(1,1,n+1,x,x,x+1);
        }
        for(auto [l,idx]:query[i]){
            auto it=lower_bound(v[i].begin(),v[i].end(),l);
            if (get(1,1,n+1,l,i)<=l || v[i].empty() || it==v[i].end())
                res[idx]=0;
            else{
                ll a=*it;
                if(a<=i) res[idx]=0;
                else res[idx]=1;
            }
        }
    }
    for(int i=1;i<=q;i++){
        if (res[i])cout<<"YES\n";
        else cout<<"NO\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...