Bad.BOY's blog

Please Help
By Bad.BOY, history, 7 years ago, In English

Hi Codeforces, Can you solve this problem?

I couldn't, But I know that you can solve

Please help me

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Consider oranges as +1 and apples as -1.

Do the partial sum on the array. Now we want to find for every i , the maximum j such that for each i <  = k <  = j, partial[k] >  = partial[i] .

You can find such j using binary search and RMQ. (This is possible with simple stack too in O(n) ).

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

For all i (1 <= i <= n) calc the largest p[i] such that for all i <= k <= p[i] count of 'p' in a[i:k] > count of 'j' in a[i:k] it can be done using prefixes and binary search

Similarly, calc s (for all (1 <= i <= n) lowest s[i] such adding fruits from i to s[i] is possible)

Make tree segment on s. Bruteforce left part of line. To find answer which starts in left you need to find the largest t such s[t] <= left for i <= t <= p[left], t can be finded by down search in tree segment

→ Reply