Little Monk

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));
		}
	}
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro