| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 160 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
You are given an array A of size N.
Let B denote the list of all N*(N+1)/2 subarray sums of A sorted in non-increasing order.
Your task is to return the Kth element in B. Since the answer can be very large return it modulo 10+7
1<=N<=10**5 1<=K<=min(N*(N+1)/2,10**5) 1<=a[i]<=10**9
apply binary search for a given mid calculate no of subarrays with sum<=mid which can be done using sliding window. now if no of such subarrays>=k then update ans=mid, high=mid-1 else low=mid
What is given mid you are referring above and calculate the no of sub arrays with sum required all sub arrays which are O(n2) results to TLE
mid is variable for binary search
int low=0,high=1e15;
int ans=-1;
while(low<=high) {
int mid=(low+high)/2;
if(check(mid)>=k)
{ ans=mid;
high=mid-1;}
else low=mid+1;
}
check (mid) represent number of subarray with sum less than or equal to mid you can calculate this in O(n)
refer this
This can be easily solved using binary search and two pointers. For a value $$$VAL$$$, it doesn't require $$$O(N^2)$$$ to count all the subarrays that have $$$sum \lt = VAL$$$, but rather $$$O(N)$$$ or $$$O(N log N)$$$ . Define $$$sum(l,r) = a[l] + ... +a[r]$$$. It's obvious that if $$$ly$$$ $$$ \lt =$$$ $$$lx$$$ $$$ \lt =$$$ $$$rx$$$ $$$ \lt =$$$ $$$ry$$$) then $$$sum(lx,rx)$$$ $$$ \lt =$$$ $$$sum(ly,ry)$$$. Define $$$next[p]$$$ as the maximum value $$$p \lt = n$$$ such that $$$sum(p,next[p]) \lt = VAL$$$ . The number of subarrays satisfy the conditions will be $$$\sum_{p=1}^{n} next[p] - p + 1$$$. It's obvious that $$$next[p] \lt = next[p + 1]$$$, so the values $$$next[p]$$$ for the whole array can be calculated in $$$O(N)$$$ using two pointers or binary search. The overall complexity is $$$O(N log^2 sum)$$$ or $$$O(N log sum)$$$