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 secondll 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;}`