### NeoYL's blog

By NeoYL, history, 2 months ago,

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the first episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are completely solved without looking at the editorial, that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).

If you want to motivate me to write a continuation (aka note 2), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Try to solve the task independently before continuing the blog.

Hint
Incomplete solution

That reduces the problem to $O(N ^ 2)$, lets optimize it!

optimization used

This allows an $O(N log N)$ solution

Code

Feel free to ask anything about the task. I will try to respond them if I am free.

• +48

 » 2 months ago, # |   +3 Auto comment: topic has been updated by NeoYL (previous revision, new revision, compare).
 » 2 months ago, # |   +3 Auto comment: topic has been updated by NeoYL (previous revision, new revision, compare).
 » 2 months ago, # |   +3 That's a great initiative, good luck!
•  » » 2 months ago, # ^ |   +6 Thanks!
 » 6 weeks ago, # |   +5 Try to solve this problem when the updates are permanent btw. Quite an interesting problem. spoilerI totally didn't read the statement wrong and solve for this instead.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 ?Is it LCT?Is there a problem link?
•  » » » 6 weeks ago, # ^ |   0 Time ComplexityMine is O(nroot(n)). About DS involvedNothing too complicated beyond what is used here.I didn't find any judge for this. I tested my solution by reversing the updates in this version of the problem.