# Find The Evil Monsters DSA Interview Problems

Find The Evil Monsters is the Data Structures and Algorithms Interview Problem asked by CodeNation and Trilogy-Innovations in their Interviews. Its difficulty level is hard. Let’s solve this problem together.

## Find The Evil Monsters Problem Statement

Given an array

$A$$A$ of

$n$$n$ elements representing the monsters and an array

$B$$B$ of

$q$$q$ elements representing the heros.

The

$i-th$$i-th$ type of monster is represented by

$A\left[i\right]\left[0\right]$$A[i][0]$,

$A\left[i\right]\left[1\right]$$A[i][1]$ and

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

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

$A\left[i\right]\left[0\right]$$A[i][0]$ to

$A\left[i\right]\left[1\right]$$A[i][1]$ and having a strength of

$A\left[i\right]\left[2\right]$$A[i][2]$.

The

$i-th$$i-th$ type of hero is represented by

$B\left[i\right]\left[0\right]$$B[i][0]$ and

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

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

$B\left[i\right]\left[0\right]$$B[i][0]$ after

$i$$i$ seconds. When the

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

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

$B\left[i\right]\left[1\right]$$B[i][1]$.

For each

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

$i-th$$i-th$ hero has completed their task.

Input

The first line of input contains two integers

$N$$N$

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

$Q$$Q$

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

The next

$n$$n$ lines contains

$3$$3$ integers

$A\left[i\right]\left[0\right],A\left[i\right]\left[1\right],A\left[i\right]\left[2\right]$$A[i][0], A[i][1], A[i][2]$

$\left(1\le A\left[i\right]\left[0\right]\le A\left[i\right]\left[1\right]\le {10}^{5};1\le A\left[i\right]\left[2\right]\le {10}^{9}\right)$$(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$$q$ lines contains

$2$$2$ integers

$B\left[i\right]\left[0\right],B\left[i\right]\left[1\right]$$B[i][0], B[i][1]$

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

Output

Print

$q$$q$ space separated integers — the

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

$i-th$$i-th$ hero has completed their task.

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

Output
11 9

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

Output
16 15 14

Note

In sample test

$1$$1$, Initially there are

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

$2nd$$2nd$ type present at coordinate

$3$$3$ having a strength of

$4$$4$. After the first operation there are

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

$2nd$$2nd$ type present at coordinate

$5$$5$ having a strength of

$4$$4$ and the monster of

$3rd$$3rd$ type present at co-ordinate

$5$$5$ having a strength of

$6$$6$. Hence there are

$9$$9$ monsters left after the second operation.

In sample test

$2$$2$, Initially there are

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

$2nd$$2nd$ type present at coordinate

$7$$7$ having a strength of

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

$4th$$4th$ type present at coordinate

$7$$7$ haying a strength of

$10$$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);
for(int A=1;A<=Q;A++)
{
cin>>query[A].first>>query[A].second;
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;
{
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;
}