Find The Evil Monsters DSA Interview Problems

Posted by admin July 11, 2023

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 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.

Input

The first line of input contains two integers

N

(1≤N≤105) and

Q

(1≤Q≤105) — 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≤A[i][0]≤A[i][1]≤105;1≤A[i][2]≤109) each describing the monsters.

The next

q lines contains

2 integers

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

(1≤B[i][0]≤105;1≤B[i][1]≤109) each describing the heroes.

Output

Print

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.

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, 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;
}