### esskk's blog

By esskk, history, 15 months ago, ,

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

• +8

 » 15 months ago, # | ← Rev. 2 →   -12 do with upper_bound() and lower_bound()
 » 15 months ago, # |   +5 U cant brute this Should do with nlogn or sth
 » 15 months ago, # |   0 can you write a link on this ploblem, please
•  » » 15 months ago, # ^ |   0 It isn't online
•  » » » 15 months ago, # ^ |   0 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
•  » » » » 15 months ago, # ^ |   0 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.
 » 14 months ago, # |   0 We can easily come up with an O(n2) DP recurrence: , where RMQ is the range maximum, and RMQ′ is the range minimum. Note that RMQ′ (i + 1, j) - (j - i) is an increasing function for a fixed j, so we can use two pointers to find all valid i. 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. If j ≥ lz, we are only going to add dpl + j - lz... r to dpj, instead of adding dpl... r. Note that lz = x + l + 1, so we can just sort our tuples by x + l + 1 in a set.This algorithm is slow if we have many tuples in our deque. However, its amortized time complexity is actually .
•  » » 13 months ago, # ^ |   0 Could u explain it a little better i dont get
 » 13 months ago, # |   0 Bump
 » 12 months ago, # |   0 Bump
 » 10 months ago, # |   0 Bump
 » 10 months ago, # |   0 bump