HackerEarth Kth smallest number again problem solution YASH PAL, 31 July 2024 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("%dn",n)#define pln(n) printf("%lldn",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("%dn",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;} coding problems solutions