Find The Evil Monsters is the Data Structures and Algorithms Interview Problem asked by
Find The Evil Monsters Problem Statement
Given an array
of
elements representing the monsters and an array
of
elements representing the heros.
The
type of monster is represented by
,
and
which means a monster of the
type is present at each integer co-ordinate from
to
and having a strength of
.
The
type of hero is represented by
and
which means a hero of strength
will appear at the integer point
after
seconds. When the
hero appears it will destroy each and every monster present at
and having a strength less than
.
For each
you have to determine the number of monsters left after the
hero has completed their task.
The first line of input contains two integers
and
— the number of monsters and the number of heroes respectively.
The next
lines contains
integers
each describing the monsters.
The next
lines contains
integers
each describing the heroes.
space separated integers — the
number should be equal to the number of monsters left after the
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
, Initially there are
monsters in total. The first hero will destroy the monster of
type present at coordinate
having a strength of
. After the first operation there are
monsters left. The second hero will destroy the monster of
type present at coordinate
having a strength of
and the monster of
type present at co-ordinate
having a strength of
. Hence there are
monsters left after the second operation.
In sample test
, Initially there are
monsters in total. The first hero will not destroy even a single monster. The second hero will destroy the monster of
type present at coordinate
having a strength of
. The third hero will destroy the monster of
type present at coordinate
haying a strength of
.
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 thought on “Find The Evil Monsters DSA Interview Problems”