Submission #1331539

#TimeUsernameProblemLanguageResultExecution timeMemory
1331539khoileCurtains (NOI23_curtains)C++20
100 / 100
1029 ms74720 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const ll M=1e9+7;
ll n,m,q,l,r;
ll seg[2000006],laz[2000006],res[1000006];
vector<ll> curs[500005];
vector<pair<ll,ll>> p[500005];
void dwn(ll id,ll l,ll r) {
    seg[id*2]=max(seg[id*2],laz[id]);
    seg[id*2+1]=max(seg[id*2+1],laz[id]);
    laz[id*2]=max(laz[id*2],laz[id]);
    laz[id*2+1]=max(laz[id*2+1],laz[id]);
    laz[id]=0;
}
void up(ll id,ll l,ll r,ll u,ll v,ll val) {
    if (v<l || r<u) return;
    if (u<=l && r<=v) {
        seg[id]=max(seg[id],val);
        laz[id]=max(val,laz[id]);
        return;
    }
    dwn(id,l,r);
    ll mid=(l+r)/2;
    up(id*2,l,mid,u,v,val);
    up(id*2+1,mid+1,r,u,v,val);
    seg[id]=min(seg[id*2],seg[id*2+1]);
}
ll get(ll id,ll l,ll r,ll u,ll v) {
    if (v<l || r<u) return 1e18;
    if (u<=l && r<=v) return seg[id];
    dwn(id,l,r);
    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 (ll i=1;i<=m;i++) {
        cin>>l>>r;
        curs[r].push_back(l);
    }
    for (ll i=1;i<=q;i++) {
        cin>>l>>r;
        p[r].push_back({l,i});
    }
    for (ll i=1;i<=n;i++) {
        for (ll l:curs[i]) {
            up(1,1,n,l,i,l);
        }
        for (auto[l,id]:p[i]) {
            if (get(1,1,n,l,i)>=l) res[id]=1;
        }
    }
    for (ll 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...