| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 161 |
| 2 | maomao90 | 160 |
| 3 | awoo | 159 |
| 4 | atcoder_official | 157 |
| 5 | -is-this-fft- | 155 |
| 5 | nor | 155 |
| 5 | adamant | 155 |
| 8 | Um_nik | 152 |
| 8 | maroonrk | 152 |
| 10 | djm03178 | 146 |
Two type of operations
Type1: replace A[i] by A[i]-1
Type2: Replace A[i] to 0.
Determine maximum length of subarray that can be obtained if all elements of subarray are zero and you can apply max operations of x and y of type 1 and 2 respectively.
Constraints: 1<=T<=7
1<=N<=1e5
0<=A[i]<=1e9
0<=Y<=1e9
0<=X<=1e14.
Reference Images: 
we can binary search on answer length of subarray
Like yeah i got his idea but i am not getting a 0(n) solution even to check if that length mid satisfies, like in detail say me how to check that??
let's say you are checking if you can find a subarray with length of at least $$$mid$$$
iterate through all subarrays of size $$$mid$$$ and keep a $$$cnt$$$ of how many $$$0$$$ elements in each subarray
if there's a subarray with $$$mid-cnt <= x+y$$$, then you can turn that whole subarray into $$$zeros$$$
there's an edge case when $$$x=0$$$, then you can only use the subarrays that starts with a $$$0$$$
this should be $$$O(n)$$$
Like i am sorry, the initial post was wrong, like see now i have corrected the question can you explain it to me now
now i'm not sure if i understand correctly...
why does the sample test gives $$$4$$$? the way i understand it should be $$$6$$$
I have changed the question its A[i]=A[i-1], its changed to A[i]=A[i]-1.
so for every subarray of size mid, smallest elements should be used first to exhaust all ops of type 1, then after that remaining elements<=y.
Sorry for the late reply :(
Lets do a different approach. For each index $$$l$$$, let it be a potential start of our subarray and find $$$f(l)$$$ as the furthest end away from l that we can turn the subarray $$$[l,f(l)]$$$ into zeros
If $$$a[l]==0$$$ and we found a potential end $$$r$$$, we pick $$$x$$$ largest elements in $$$[l,r]$$$ and apply opertaion $$$1$$$ to turn them to zeros, and the other elements we can chip away with operation $$$2$$$. So to be able to turn $$$[l,r]$$$ into zeros, we need to satisfy $$$Sum(l,r)-SumOfBig(l,r)<=y$$$, with $$$SumOfBig$$$ meaning the sum of the X biggest elements in $$$[l,r]$$$
If $$$a[l]!=0$$$,we use up one of the first type operation to make it $$$0$$$, and find $$$f(l)$$$ similarly like case above
$$$Sum(l,r)$$$ can be done in $$$O(1)$$$ with prefix sum; and we can find $$$SumOfBig(l,r)$$$ in $$$O(log(n)^2)$$$ with binary search, combined with Persistent Segment Tree or Persistent Fenwick Tree.
Our complexity for each potential $$$r$$$ is $$$O(log(n)^2)$$$ so we cant afford another binary search. Use 2 pointers instead.
However there's an easy mistake to fall into. Unlike normal 2 pointers, here $$$f(l)$$$ can be less than $$$f(l+1)$$$ because we must waste a first type operation if the second case occurs for $$$l+1$$$. So we need to do 2 pointers seperately for the 2 cases. I guess my explanation for doing the 2 pointers seperately might be unclear, if you are not sure about it you can ask later :D
Edit: just finished dinner :) my solution above is $$$O(n*log^2)$$$ but we can inprove it to $$$O(n*log)$$$
instead of using persistent data structures combined with binary search, as you move the pointers you can insert elements into a BST(for example Treap) or a skiplist
Is this an ongoing online assessment?
No completed yesterday night.
Auto comment: topic has been updated by conan45 (previous revision, new revision, compare).
Auto comment: topic has been updated by conan45 (previous revision, new revision, compare).
You can work this with 2 pointers maintaining the start and end points of a subarray while also keeping Y largest elements that are present in that subarray which are done by type-2 operation and making sure that all the elements that are not a part of Y largest elements are done by type-1 operation.