Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

esskk's blog

By esskk, history, 5 months ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

»
5 months ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

do with upper_bound() and lower_bound()

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

U cant brute this Should do with nlogn or sth

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can you write a link on this ploblem, please

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It isn't online

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could u explain it a little better i dont get

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bump

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Bump

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Bump