Find The Evil Monsters is the Data Structures and Algorithms Interview Problem asked by

## Find The Evil Monsters Problem Statement

Given an array

$A$ of

$n$ elements representing the monsters and an array

$B$ of

$q$ elements representing the heros.

The

$i-th$ type of monster is represented by

$A[i][0]$,

$A[i][1]$ and

$A[i][2]$ which means a monster of the

$i-th$ type is present at each integer co-ordinate from

$A[i][0]$ to

$A[i][1]$ and having a strength of

$A[i][2]$.

The

$i-th$ type of hero is represented by

$B[i][0]$ and

$B[i][1]$ which means a hero of strength

$B[i][1]$ will appear at the integer point

$B[i][0]$ after

$i$ seconds. When the

$i-th$ hero appears it will destroy each and every monster present at

$B[i][0]$ and having a strength less than

$B[i][1]$.

For each

$i$ you have to determine the number of monsters left after the

$i-th$ hero has completed their task.

The first line of input contains two integers

$N$

$(1\le N\le {10}^{5})$ and

$Q$

$(1\le Q\le {10}^{5})$ — the number of monsters and the number of heroes respectively.

The next

$n$ lines contains

$3$ integers

$A[i][0],A[i][1],A[i][2]$

$(1\le A[i][0]\le A[i][1]\le {10}^{5};1\le A[i][2]\le {10}^{9})$ each describing the monsters.

The next

$q$ lines contains

$2$ integers

$B[i][0],B[i][1]$

$(1\le B[i][0]\le {10}^{5};1\le B[i][1]\le {10}^{9})$ each describing the heroes.

$q$ space separated integers — the

$i-th$ number should be equal to the number of monsters left after the

$i-th$ hero has completed their task.

3 2 1 3 7 2 5 4 4 8 6 3 5 5 8

11 9

4 3 2 5 8 5 8 6 3 6 9 7 10 10 2 7 7 9 7 11

16 15 14

In sample test

$1$, Initially there are

$12$ monsters in total. The first hero will destroy the monster of

$2nd$ type present at coordinate

$3$ having a strength of

$4$. After the first operation there are

$11$ monsters left. The second hero will destroy the monster of

$2nd$ type present at coordinate

$5$ having a strength of

$4$ and the monster of

$3rd$ type present at co-ordinate

$5$ having a strength of

$6$. Hence there are

$9$ monsters left after the second operation.

In sample test

$2$, Initially there are

$16$ monsters in total. The first hero will not destroy even a single monster. The second hero will destroy the monster of

$2nd$ type present at coordinate

$7$ having a strength of

$6$. The third hero will destroy the monster of

$4th$ type present at coordinate

$7$ haying a strength of

$10$.

### Find The Evil Monsters Problem Solution C++

```
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
class BIT
{
private:
int N;
vector<int> BITS;
public:
void init(int n)
{
N=n;
BITS.resize(N+1);
}
int query(int X)
{
int res=0;
while(X)
{
res+=BITS[X];
X-=(X&-X);
}
return res;
}
void update(int X,int delta)
{
while(X<=N)
{
BITS[X]+=delta;
X+=(X&-X);
}
return ;
}
};
signed main()
{
int N,Q;
cin>>N>>Q;
vector< vector<int> > start(100099),finish(100099);
int tot=0;
set<int> st;
for(int A=1;A<=N;A++)
{
int x,y,z;
cin>>x>>y>>z;
start[x].push_back(z);
finish[y].push_back(z);
tot+=y-x+1;
st.insert(z);
}
unordered_map<int,int> maps;
vector< pii > query(Q+1);
vector< vector<pii> > ask(100099);
for(int A=1;A<=Q;A++)
{
cin>>query[A].first>>query[A].second;
ask[query[A].first].pb({query[A].second,A});
st.insert(query[A].second);
}
int idx=1;
for(auto A:st)
{
maps[A]=idx++;
}
vector<int> ans(Q+1,0);
BIT tree;
tree.init(200099);
for(int A=1;A<=100000;A++)
{
for(auto B:start[A])
{
B=maps[B];
tree.update(B,1);
}
int pre=0;
for(auto B:ask[A])
{
B.first=maps[B.first];
if(B.first<=pre)
continue;
ans[B.second]=tree.query(B.first-1)-tree.query(pre);
pre=B.first;
}
for(auto B:finish[A])
{
B=maps[B];
tree.update(B,-1);
}
}
for(int A=1;A<=Q;A++)
{
tot-=ans[A];
cout<<tot<<" ";
}
cout<<endl;
return 0;
}
```

## 1 Comment