When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

m8.pie's blog

By m8.pie, 4 years ago, In English

Imagine the situation when we want to find such $$$a_j$$$ for any $$$a_i$$$ which will satisfy this:

$$$a_i > a_j$$$
$$$i < j$$$

Thanks to shufl999dka we know solution for this task with $$$O(n)$$$ complexity.

Solution

Imagine now the situation, when we want to find such $$$a_j$$$ for any $$$x$$$ and $$$[l; r)$$$, which will satisfy this:

$$$a_j < x$$$
$$$l \leq j < r$$$
$$$j\;is\;less\;possible$$$

First solution I developed was $$$O(n\log^2{n})$$$ complexity and had such algorithm:

Solution

But thanks to MrDindows and bicsi we have solution with $$$O(\log{n})$$$ complexity.

Solution

It is possible to see this algorithms working on concrete task: 1237D - Balanced Playlist

Solution $$$O(n\log^2{n})$$$ complexity is 732 ms — 62741630

Solution $$$O(n\log{n})$$$ complexity is 77 ms — 62881402

If you have more efficient solution for any of these two tasks then write here in comments.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

You could binary search directly on segment tree to achieve $$$log(N)$$$ complexity, using your very same method

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I think we can use Cartesian tree to solve it in O(n).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Can't you explain me how exactly? It is interesting enough idea.

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

You can use sparse table which will give minimum in O(1) and it will be total O(NlogN).