Calculate number of ways to partition array in groups of consecutive elements,so that for each group following condition holds:the length of group is not less than minimum element in that group and length of group is not greater than maximum element in that group.Each element must belong to exactly one group. Constraints: N <= 5*10^5 Ai <= 10^9

do with upper_bound() and lower_bound()

U cant brute this Should do with nlogn or sth

can you write a link on this ploblem, please

It isn't online

If this problem is related to some other contest that is still going on, then most likely no one will help you before it's over. Therefore, we need to know where this task comes from, otherwise it will be dishonest in relation to other participants

Oh ok sry. It was on Serbia's IOI team selection,but they didn't upload it online(for purpose of grading for example).I thought that Taylor_Swift asked for link to send it for grading.I am just curious about solution because no one has solved it on-site.

We can easily come up with an

O(n^{2}) DP recurrence: , whereRMQis the range maximum, andRMQ′ is the range minimum. Note thatRMQ′ (i+ 1,j) - (j-i) is an increasing function for a fixedj, so we can use two pointers to find all validi.We can dynamically maintain the suffix maxima as we use the two pointers algorithm using a deque of tuples

`(left end, right end, maximum)`

(shortened to`(l, r, x)`

). We are now going to add an extra field`lz`

to our tuple. Ifj≥lz, we are only going to adddp_{l + j - lz... r}todp_{j}, instead of addingdp_{l... r}. Note thatlz=x+l+ 1, so we can just sort our tuples byx+l+ 1 in a set.This algorithm is slow if we have many tuples in our deque. However, its amortized time complexity is actually .

Could u explain it a little better i dont get

Bump

Bump

Bump

bump