ACTIV - Activities - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : ACTIV

👉 Hint : Binary Search N times

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 100000000
unordered_map<ll,ll> m;
int main()
{
    ll n;
    vector<pair<ll,ll> >v;
 
    while(1)
    {
        ll x,y,t;
        cin>>n;
        if(n==-1)
            break;
        v.clear();
        m.clear();
        for(ll i=1;i<=n;i++)
        {
            cin>>x>>y;
            v.push_back(make_pair(y,x));     //pair(end_time,start_time)
        }
        sort(v.begin(),v.end());
        m[0]=0;
        for(ll i = 0;i < v.size();i++)
        {
            x=v[i].second;
            y=v[i].first;
            ll l=-1;
            ll hi=i-1;
            ll mid;
            while(l<hi)
            {
                mid=l+(hi-l+1)/2;
                if(v[mid].first<=x)
                    l=mid;
                else
                    hi=mid-1;
            }
            x=v[hi].first;
            if(m[y]==0)
            {
                m[y]=m[v[i-1].first];
            }
            m[y]=(m[y]+1+m[x])%mod;
        }
        cout<<setfill('0')<<setw(8)<<m[y]<<endl;
 
 
 
    }
}

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

About Utkarsh Gupta

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.