Submission #1323538

#TimeUsernameProblemLanguageResultExecution timeMemory
1323538aryanCurtains (NOI23_curtains)C++20
0 / 100
1 ms332 KiB
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

const int inf = 1e9;
const int N = 100 + 5;
vector<int> tree(4 * N,inf);
vector<int> lazy(4 * N,inf);

void dolazy(int ind){
    tree[2 * ind] = min(tree[2 * ind],lazy[ind]); 
    tree[2 * ind + 1] = min(tree[2 * ind + 1],lazy[ind]);

    lazy[2 * ind] = min(lazy[2 * ind],lazy[ind]);
    lazy[2 * ind + 1] = min(lazy[2 * ind + 1],lazy[ind]);
}

void update(int ind,int nl,int nr,int l,int r){
    if(nl > r || l > nr) return;
    if(l <= nl && r >= nr){
        tree[ind] = min(tree[ind],r);
        lazy[ind] = min(lazy[ind],r);
        return;
    }
    dolazy(ind);
    int mid = (nl + nr) / 2;
    update(2 * ind,nl,mid,l,r);
    update(2 * ind + 1,mid + 1,nr,l,r);
    tree[ind] = max(tree[2 * ind],tree[2 * ind + 1]);
}

int query(int ind,int nl,int nr,int l,int r){
 if(nl > r || l > nr) return 0;
    if(l <= nl && r >= nr){
        return tree[ind];
    }
    dolazy(ind);
    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;
    vector<pair<int,int>> rn(m);
    for(int i = 0;i < m;i++){
        cin >> rn[i].first >> rn[i].second;
    }
    sort(rn.begin(),rn.end(),greater<pair<int,int>>());
    vector<Data> que(q);
    for(int i = 0;i < q;i++){
        cin >> 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 && que[i].l <= rn[j].first){
            update(1,0,n,rn[j].first,rn[j].second);
            j ++;
        }
        if(query(1,0,n,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...