HackerEarth Kth smallest number again problem solution

In this HackerEarth Kth smallest number again problem solution Dexter was good in finding the K th smallest number from a set of numbers. He thought he could solve any problem related to K th smallest number. His friend Pipi challenged him with a problem.

He gave him various ranges of number, These numbers were arranged in increasing order(only distinct numbers to be taken into account). Now he asked him to find the K th smallest number in the sequence, again and again.

HackerEarth Kth smallest number again problem solution.

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
using namespace std;
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair
#define si(n) scanf("%d",&n)
#define pi(n) printf("%d ",n)
#define pin(n) printf("%d\n",n)
#define pln(n) printf("%lld\n",n)
#define pl(n) printf("%lld ",n)
#define sl(n) scanf("%lld",&n)
#define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define mod (int)(1e9 + 7)
#define ll long long int
#define F first
#define S second
ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;} 

vector<pair<ll,ll> > arr,brr;
vector<ll> bin;
void modify()
{
    ll i,sz,a,b,tp=0;
    brr.pb(arr[0]);
    sz=arr.size();
    FOR(i,1,sz)
    {
        a=arr[i].F;
        b=arr[i].S;
        if(a>brr[tp].S)
        {
            tp++;
            brr.pb(mp(a,b));
        }
        else
        {
            brr[tp].S=max(brr[tp].S,b);
        }
    }
}
ll binary(ll sz, ll val)
{
    ll low=0,high=sz,mid,calc;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(bin[mid]<val && (mid==sz || bin[mid+1]>=val))
        {
            if(mid==sz)
                return -1;
            else
            {
                calc=val-bin[mid];
                return brr[mid].F+calc-1;
            }
        }
        else if(val>bin[mid])
            low=mid+1;
        else
            high=mid-1;
    }
    return -1;
}
int main()
{
    ll t,n,q,a,b,sz,i,calc,k;
    sl(t);
    while(t--)
    {
        arr.clear();
        brr.clear();
        bin.clear();
        sl(n);
        sl(q);
        rep(i,n)
        {
            sl(a);
            sl(b);
            arr.pb(mp(a,b));
        }
        sort(arr.begin(),arr.end());
        modify();
        sz=brr.size();
        bin.pb(0);
        rep(i,sz)
        {
            calc=brr[i].S-brr[i].F+1+bin[i];
            bin.pb(calc);
        }
        rep(i,q)
        {
            sl(k);
            calc=binary(sz,k);
            pln(calc);
        }
    }
    return 0;
}

Second solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define sz size()

typedef long long int LL;
typedef pair<int, int > pii;
typedef pair<LL, LL > pll;
typedef vector<int > vi;

vector<pll > inp, v;

int bs(LL k) {

    int res = -1;
    int lo = 0;
    int hi = v.sz - 1;

    while(lo <= hi) {
        int mi = (lo + hi) >> 1;
        if(v[mi].second >= k) {
            res = mi;
            hi = mi - 1;
        } else {
            lo = mi + 1;
        }
    }

    return res;

}

int main() {
    int t;
    S(t);
    // assert(t >= 1 && t <= 10);
    while(t--) {
        inp.clear(); v.clear();
        int n,q;
        S2(n,q);
        assert(n >= 1 && n <= 100000);
        assert(q >= 1 && q <= 100000);
        rep(i,0,n) {
            LL x,y;
            cin >> x >> y;
            assert(x >= -1000000000000000000LL && x <= 1000000000000000000LL);
            assert(y >= -1000000000000000000LL && y <= 1000000000000000000LL);
            inp.push_back(make_pair(x,y));
        }
        sort(all(inp));

        LL a,b;
        a = b = -1000000000000000001LL;
        LL cnt = 0;

        rep(i,0,n) {
            if(inp[i].first > b) {
                a = inp[i].first;
                b = inp[i].second;
                cnt += b - a + 1;
                v.push_back(make_pair(b,cnt));
            } else if(inp[i].second <= b) {

            } else {
                a = b + 1;
                b = inp[i].second;
                cnt += b - a + 1;
                v.push_back(make_pair(b,cnt));
            }
        }

        while(q--) {
            LL k;
            cin >> k;
            assert(k >= 1);
            if(v.back().second < k) {
                P(-1);
                continue;
            }
            int idx = bs(k);
            // P(idx);
            cout << v[idx].first - v[idx].second + k << endl;
        }
    }

    return 0;
}