Submission #1323463

#TimeUsernameProblemLanguageResultExecution timeMemory
1323463aryanCurtains (NOI23_curtains)C++20
9 / 100
1599 ms105952 KiB
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

const int N = 1e5;
vector<int> tree(4 * N,N + 5);
vector<multiset<int>> val(4 * N);

void update(int ind,int nl,int nr,int l,int r,int v){
    if(nl > r || l > nr) return;
    if(l <= nl && r >= nr){
        if(v == 1) val[ind].insert(r);
        if(v == -1) val[ind].erase(val[ind].find(r));
        return;
    }
    int mid = (nl + nr) / 2;
    update(2 * ind,nl,mid,l,r,v);
    update(2 * ind + 1,mid + 1,nr,l,r,v);
    tree[ind] = max(min(*val[2 * ind].begin(),tree[2 * ind]),min(*val[2 * ind + 1].begin(),tree[2 * ind + 1]));
}

int ma;
int query(int ind,int nl,int nr,int l,int r){
    if(nl > r || l > nr) return 0;
    if(l <= nl && r >= nr){
        int mini =  min(ma,tree[ind]);
        mini = min(mini,*val[ind].begin());
        return mini;
    }
    ma = min(ma,*val[ind].begin());
    int mid = (nl + nr) / 2;
    return max(query(2 * ind,nl,mid,l,r),
    query(2 * ind + 1,mid + 1,nr,l,r));
}

struct Data{
    int l,r,i;
    Data() {};
    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;
    for(int i = 0;i < 4 * n;i++){
        val[i].insert(N + 5);
    }
    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 --;
        update(1,0,n - 1,rn[i].first,rn[i].second,1);
    }
    sort(rn.begin(),rn.end());
    vector<Data> que(q);
    for(int i = 0;i < q;i++){
        cin >> que[i].l >> que[i].r;
        que[i].l --;
        que[i].r --;
        que[i].i = i;
    }
    sort(que.begin(),que.end());

    int j = 0;
    vector<bool> ans(q);
    for(int i = 0;i < q;i++){
        while(j < n && rn[j].first < que[i].l){
            update(1,0,n - 1,rn[j].first,rn[j].second,-1);
            j ++;
        }
        ma = N + 5;
        if(query(1,0,n - 1,que[i].l,que[i].r) > que[i].r){
            ans[que[i].i] = false;
        }else{
            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...