Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Find the row with max ones
TraiectorieIdeala
1568-1644 Solar eclipses, make 1617(8) and 1620(12) Lunar eclipses the same as Chinese records
1234
Simulare 2022 SIII, 1
задача new
5
Wipro Problem 1
Hi
HashTabFold