➤ Problem Link : BGSHOOT
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll st[600002];
ll arr[300001];
void build(ll v, ll s, ll e)
{
if(s==e)
{
st[v]=arr[s];
return ;
}
ll mid=(s+e)/2;
build(2*v,s,mid);
build(2*v+1,mid+1,e);
st[v]=max(st[2*v],st[2*v+1]);
}
ll query(ll v, ll s, ll e, ll l, ll r)
{
if(s>r || e<l)
return 0;
if(s>=l && e<=r)
return st[v];
ll mid=(s+e)/2;
return max(query(2*v,s,mid,l,r),query(2*v+1,mid+1,e,l,r));
}
int main()
{
int n,q;
cin>>n;
map<ll,ll> mp;
unordered_map<ll,ll> newCoord;
ll x,y;
for(ll i=1;i<=n;i++)
{
cin>>x>>y;
mp[x]++;
if(mp.find(y)==mp.end())
mp[y]=0;
mp[y+1]--;
}
cin>>q;
pair<ll,ll> qry[q+1];
for(ll i=1;i<=q;i++)
{
cin>>x>>y;
if(mp.find(x)==mp.end())
mp[x]=0;
if(mp.find(y)==mp.end())
mp[y]=0;
qry[i]=make_pair(x,y);
}
ll curr=0;
ll t=0;
for(auto it=mp.begin();it!=mp.end();it++)
{
curr+=it->second;
t++;
newCoord[it->first]=t;
arr[t]=curr;
}
build(1,1,t);
for(int i=1;i<=q;i++)
{
cout<<query(1,1,t,newCoord[qry[i].first],newCoord[qry[i].second])<<"\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.