D.E.Shaw Binary Search Question, C++ (gcc)

D.E.Shaw Binary Search Question

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

ll CountOfSmallerOrEqualSumSubarray (vector<int>& arr, ll sum) {
	int n = arr.size();
	
	vector<ll> prefix_sum(n+1, 0);
	for (int j = 1; j <= n; j ++) 
		prefix_sum[j] = prefix_sum[j-1] + arr[j-1];
	
	ll result = 0;
	for (int j = 1; j <= n; j ++) {
		ll can = prefix_sum[j] - sum;
		int ind = lower_bound (prefix_sum.begin(), prefix_sum.end(), can) - prefix_sum.begin();
		
		result += (j - ind);
	}
	return result;
}

ll GetKthLargest(vector<int> &arr, int k) {
	ll l = 0, r = 1e18;
    
	while (l < r) {
		ll m = (l+r)/2;
		ll smaller_or_equal_m = CountOfSmallerOrEqualSumSubarray (arr, m);
		        
		if (smaller_or_equal_m < k) l = m+1;
		else r = m;
	}
	
	return l;
}

int main() {
    vector<int> arr = {1, 2, 3, 4}; 
    cout << GetKthLargest (arr, 6) << endl;
    return 0;
}

/*
(0, 0) - 1
(0, 1) - 3
(0, 2) - 6
(0, 3) - 10
(1, 1) - 2
(1, 2) - 5
(1, 3) - 9
(2, 2) - 3
(2, 3) - 7
(3, 3) - 4

[1 2 3 3 4 5 6 7 9 10] 
*/


run \| edit \| history \| help	0