Submission #1323476

#TimeUsernameProblemLanguageResultExecution timeMemory
1323476aryanCurtains (NOI23_curtains)C++17
80 / 100
1627 ms843204 KiB
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
const int inf = 1e9;

struct Vertex{
    Vertex () {}
    Vertex* l;
    Vertex* r;
    int v;
    int lz;
};

Vertex* build(int nl,int nr){
    if(nl == nr){
        Vertex* nv = new Vertex();
        nv->v = inf;
        nv->lz = inf;
        return nv;
        // return new Vertex(a[nl]);
    }else{
        int mid = (nl + nr) / 2;
        Vertex* nv = new Vertex();
        nv-> l = build(nl,mid);
        nv-> r = build(mid + 1,nr);
        nv->v = max(nv->l->v,nv->r->v);
        nv->lz = inf;
        return nv;
        // return new Vertex(build(nl,mid,a),build(mid + 1,nr,a));
    }
}

Vertex* update(Vertex* v,int nl,int nr,int &l,int &r){
    if(nl > r || l > nr) return nullptr;
    if(l <= nl && r >= nr){
        Vertex* nv = new Vertex();
        nv->l = v->l;
        nv->r = v->r;
        nv->v = min(r,v->v);
        nv->lz = min(v->lz,r);
        return nv;
    }
    int mid = (nl + nr) / 2;
    Vertex* nv = new Vertex();
    nv->lz = v->lz;
    Vertex *nle = update(v->l,nl,mid,l,r);
    Vertex *nre = update(v->r,mid + 1,nr,l,r);
    if(nle != nullptr){
        nv->l = nle;
    }else{
        nv->l = v->l;
    }
    if(nre != nullptr){
        nv->r = nre;
    }else{
        nv->r = v->r;
    }
    nv->v = min(v->v,max(nv->l->v,nv->r->v));
    return nv;
}

int query(Vertex* v,int nl,int nr,int &l,int &r,int mini){
    if(nl > r || l > nr) return 0;
    if(l <= nl && r >= nr){
        return min(mini,v->v);
    }
    int mid = (nl + nr) / 2;
    return max(query(v->l,nl,mid,l,r,min(mini,v->lz)),
    query(v->r,mid + 1,nr,l,r,min(mini,v->lz)));
}

struct Data{
    Data () {};
    int l,r,i;
    bool operator<(Data &d){
        return d.l > this->l;
    }
};

int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,q;
    cin >> n >> m >> q;
    vector<pair<int,int>> rn(m);
    for(int i = 0;i < m;i++){
        cin >> rn[i].first >> rn[i].second;
        rn[i].first --;
        rn[i].second --;
    }
    sort(rn.begin(),rn.end());
    vector<Vertex*> roots;
    roots.push_back(build(0,n));
    for(int i = m - 1;i >= 0;i--){
        roots.push_back(update(roots[m - i - 1],0,n,rn[i].first,rn[i].second));
    }

    vector<Data> que(q);
    for(int i = 0;i < q;i++){
        // cin >> que[i].first >> que[i].second; 
        cin >> que[i].l >> que[i].r;
        que[i].l --;
        que[i].r --;
        que[i].i = i;
    }
    sort(que.begin(),que.end());
    vector<bool> ans(q);
    int j = 0;
    for(int i = 0;i < q;i++){
        while(j < m && rn[j].first < que[i].l){
            j ++;
        }
        int mini = inf;
        if(query(roots[m - j],0,n,que[i].l,que[i].r,mini) > que[i].r){
            // cout << "NO\n";
            ans[que[i].i] = false;
        }else{
            // cout << "YES\n";
            ans[que[i].i] = true;
        }
    }
    for(int i = 0;i < q;i++){
        cout << (ans[i] ? "YES\n" : "NO\n");
    }

    return 0;
}
#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...