pretending's blog

How to solve this problem in O(log(n)*n) or less?
By pretending, history, 3 years ago, In English

I am stuck at this problem currently.

Problem link

I have tried a O(n^2) approach but the accepted solution is supposedly O(log(n)*n) or less. How do solve this?

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

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why not just link the problem instead of copy-pasting the statement?

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

This problem seems like this problem: https://atcoder.jp/contests/dp/tasks/dp_z

You can solve this problem using a Li-Chao tree.

→ Reply