➤ Problem Link : POSTERS
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
ll st[40000001];
bool lazy[40000001];
pair<ll,ll> arr[200001];
void build(ll v, ll l, ll r)
{
if(l==r)
{
lazy[v]=0;
st[v]=0;
return ;
}
ll mid=(l+r)/2;
build(2*v,l,mid);
build(2*v+1,mid+1,r);
lazy[v]=0;
st[v]=0;
}
void propagateLazy(ll v, ll l, ll r)
{
if(l!=r)
{
lazy[2*v]=1;
lazy[2*v+1]=1;
}
st[v]=(r-l+1);
}
void update(ll v, ll s , ll e, ll l, ll r)
{
if(lazy[v])
propagateLazy(v,s,e);
if(s>r || e<l)
return;
if(s>=l && e<=r)
{
lazy[v]=1;
propagateLazy(v,s,e);
return;
}
ll mid=(s+e)/2;
update(2*v,s,mid,l,r);
update(2*v+1,mid+1,e,l,r);
st[v]=st[2*v]+st[2*v+1];
}
ll query(ll v, ll s, ll e, ll l, ll r)
{
if(lazy[v])
propagateLazy(v,s,e);
if(s>r || e<l)
return 0;
if(s>=l && e<=r)
return st[v];
ll mid=(s+e)/2;
return query(2*v,s,mid,l,r)+query(2*v+1,mid+1,e,l,r);
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll mx=pow(10,7);
for(ll i=1;i<=n;i++)
cin>>arr[i].first>>arr[i].second;
build(1,1,mx);
ll cnt=0;
ll curr;
for(int i=n;i>=1;i--)
{
curr=query(1,1,mx,arr[i].first,arr[i].second);
if(curr<arr[i].second-arr[i].first+1)
cnt++;
update(1,1,mx,arr[i].first,arr[i].second);
}
cout<<cnt<<"\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.