➤ Problem Link : 1257D. Yet Another Monster Killing Problem
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin>>t;
while(t--)
{
ll n,m,p,s;
cin>>n;
ll monster[n];
for(int i=0;i<n;i++)
cin>>monster[i];
cin>>m;
map<ll,ll> maxEnd;
for(int i=0;i<m;i++)
{
cin>>p>>s;
if(maxEnd.find(p)==maxEnd.end())
maxEnd[p]=s;
else
maxEnd[p]=max(maxEnd[p],s);
}
auto it=maxEnd.end();
it--;
ll maxi=(*it).second;
for(;it!=maxEnd.begin();it--)
{
if(maxi>(*it).second)
(*it).second=maxi;
else
maxi=(*it).second;
}
(*it).second=max((*it).second,maxi);
/* for(auto s: maxEnd)
cout<<s.first<<" "<<s.second<<endl;*/
ll i=0,j=0;
ll ans=0;
bool flag=0;
while(i<n)
{
j=i;
ll mx=-1;
while(j<n)
{
mx=max(mx,monster[j]);
auto itr=maxEnd.lower_bound(mx);
if(itr==maxEnd.end())
{
flag=1;
break;
}
if((*itr).second >= j-i+1)
{
j++;
}
else
break;
}
if(flag)
break;
ans++;
i=j;
}
if(flag)
cout<<"-1\n";
else
cout<<ans<<"\n";
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.