HackerEarth Eerie Planet problem solution

In this HackerEarth Eerie Planet problem solution, You own a club on an eerie planet. The day on this planet comprises H hours. You appointed C crew members to handle the huge crowd that you get, being the best club on the planet. Each member of the crew has a fixed number of duty hours to work. There can be multiple or no crew members at work at any given hour of the day.

Being on a weird planet, the rules of this club cannot be normal. Each member of the crew only allows people who are taller than him to enter the club when he is at work.

Given the schedule of work and the heights of the crew members, you have to answer Q queries. Each query specifies the time of entry and height of a person who is visiting the club. You have to answer if the person will be allowed to enter the club or not.

HackerEarth Eerie Planet problem solution.

#include <bits/stdc++.h>
using namespace std;

#define ii pair<int, int>
#define ff first 
#define ss second 

int guardHeights[100005];
int queryHeights[100005];
int invalid[100005];
int ans[100005];

struct node{
    bool query;
    int timer;
    bool start;
    int id;
    node(bool query, int timer, bool start, int id) : query(query), timer(timer), start(start), id(id) { }
};

bool cmp(node a, node b){
    if(a.timer != b.timer)
        return a.timer < b.timer;
    else
        return a.query < b.query;
}

int main(){
    int i,j,h,c,q,s,e,max_h;
    scanf("%d %d %d", &h, &c, &q);
    vector<node> timeSortedQueries;
    priority_queue<ii> pq;
    ii tp;

    for(i = 0; i < c; i++){
        scanf("%d %d %d", &guardHeights[i], &s, &e);
        timeSortedQueries.push_back(node(0, s, 1, i));
        timeSortedQueries.push_back(node(0, e + 1, 0, i));
    }
    for(i = 0; i < q; i++){
        scanf("%d %d", &queryHeights[i], &s);
        timeSortedQueries.push_back(node(1, s, 0, i));
    }
    sort(timeSortedQueries.begin(), timeSortedQueries.end(), cmp);
    for(auto el : timeSortedQueries){
        if(!el.query){
            if(el.start)
                pq.push({guardHeights[el.id], el.id});
            else
                invalid[el.id] = 1;
        }
        else{
            max_h = 0;
            while(!pq.empty()){
                tp = pq.top();
                if(!invalid[tp.ss]){
                    max_h = tp.ff;
                    break;
                }
                else
                    pq.pop();
            }
            ans[el.id] = (queryHeights[el.id] > max_h);
        }
    }
    for(i = 0; i < q; i++)
        printf("%s\n", ans[i] ? "YES" : "NO");
    return 0;
}

Second solution

#include <bits/stdc++.h>
#define ff first
#define ss second
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

 
using namespace std;



void verify(int n, int l, int r){
    assert(n >= l && n <= r);
}


const int N = 100002;
int H, C, Q, cc, ans[N], tree[12*N], lazy[12*N];
int crew[N][3], qarr[N][2];
map<int, int> compress;


void update(int node, int s, int e, int lo, int hi, int val){
    if(s > e || lo > hi)    return;
    if(lazy[node] != 0){
        tree[node] = max(tree[node], lazy[node]);
        if(s != e){
            lazy[LEFT(node)] = max(lazy[LEFT(node)], lazy[node]);
            lazy[RIGHT(node)] = max(lazy[RIGHT(node)], lazy[node]);
        }
        lazy[node] = 0;
    }
    if(s > hi || lo > e)    return;
    if(s >= lo && e <= hi){
        tree[node] = max(tree[node], val);
        if(s != e){
            lazy[LEFT(node)] = max(lazy[LEFT(node)], val);
            lazy[RIGHT(node)] = max(lazy[RIGHT(node)], val);
        }
        return;
    }
    int mid = (s+e)/2;
    update(LEFT(node), s, mid, lo, hi, val);
    update(RIGHT(node), mid+1, e, lo, hi, val);
    tree[node] = max(tree[LEFT(node)], tree[RIGHT(node)]);
}


int query(int node, int s, int e, int pos){
    if(s > e)   return 0;
    if(lazy[node] != 0){
        tree[node] = max(tree[node], lazy[node]);
        if(s != e){
            lazy[LEFT(node)] = max(lazy[LEFT(node)], lazy[node]);
            lazy[RIGHT(node)] = max(lazy[RIGHT(node)], lazy[node]);
        }
        lazy[node] = 0;
    }
    if(s > pos || pos > e)  return 0;
    if(s == e)  return tree[node];
    int mid = (s+e)/2;
    int a = query(LEFT(node), s, mid, pos);
    int b = query(RIGHT(node), mid+1, e, pos);
    return max(a, b);
}


 
int main(){

    scanf("%d%d%d", &H, &C, &Q);
    verify(H, 1, 100000*10000);
    verify(C, 1, 100000);
    verify(Q, 1, 100000);

    for(int i=1;i<=C;i++){
        scanf("%d%d%d", &crew[i][0], &crew[i][1], &crew[i][2]);
        verify(crew[i][0], 1, 10000*1000);
        verify(crew[i][1], 1, H);
        verify(crew[i][2], 1, H);
        compress[crew[i][1]];
        compress[crew[i][2]];
    }

    for(int i=1;i<=Q;i++){
        scanf("%d%d", &qarr[i][0], &qarr[i][1]);
        verify(qarr[i][0], 1, 10000*1000);
        verify(qarr[i][1], 1, H);
        compress[qarr[i][1]];
    }

    cc = 0;
    for(auto &it : compress)
        it.ss = ++cc;
    for(int i=1;i<=C;i++){
        update(1, 1, cc, compress[crew[i][1]], compress[crew[i][2]], crew[i][0]);
    }

    for(int i=1;i<=Q;i++){
        if(query(1, 1, cc, compress[qarr[i][1]]) < qarr[i][0])  printf("YES\n");
        else  printf("NO\n");
    }

    return 0;
}