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.


Hacker Kth smallest number again problem solution


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