QUESTION

Little monk has travelled across the world but he has never seen a place like byteland. The mountains in the byteland have a unique order. Height of ith mountain is represented by an interval (li,ri) i.e. the height of the mountain is in increasing order, li,li+1,li+2,….,ri. The heights of mountains are such that if i<j then ri<lj. Now the little monk wants to know xth smallest height in the byteland.\nNote: x will be always in the given range of intervals.\nInput Format:\nFirst line contains two space separated integers, N (1N105) and Q(1Q105), number of mountains and number of queries.\nNext N lines contains two separated integers each, li and ri (1li,ri1018). ith line contains the starting height and the end height of the ith mountain.\nNext Q lines contains one integer, x (1×1018), each, denoting the queries.\nOutput Format:\nFor each query, print xth smallest height in the byteland\n\n.

“TESTCASE_1”: “3 3\n1 10\n11 20\n21 30\n5\n15\n25\n###—###SEPERATOR—###—\n5\n15\n25”, “TESTCASE_2”: “4 4\n2 14\n9 22\n21 34\n44 65\n6\n20\n34\n###—###SEPERATOR—###—\n7\n15\n27\n27”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <stdio.h>
#define ll long long int
 
int binarySearch(ll arr[], ll x, int l, int h) {
	int mid = l + (h - l) / 2;
	if (l < h) {
		if (arr[mid] > x) return binarySearch(arr, x, l, mid);
		if (arr[mid] < x) return binarySearch(arr, x, mid+1, h);
		return mid;
	}
	return mid;
}
 
int main() {
	int n, Q, i, pos;
	scanf("%d%d", &n, &Q);
	ll Height[n], mountain[n], x;
	for (i = 0; i < n; ++i) {
		scanf("%lld %lld",&Height[i],&mountain[i]);
		mountain[i] -= (Height[i] - 1);
		if (i > 0) mountain[i] += mountain[i-1];
	}
	while (Q--) {
		scanf("%lld",&x);
		if (x <= mountain[0])
			printf("%lld\n", Height[0] + x - 1);
		else {
			pos = binarySearch(mountain, x, 0, n);
			printf("%lld\n", Height[pos] + (x - mountain[pos-1] - 1));
		}
	}
}