Problem D in EPIC Institute of Technology Round Summer 2024

I'm not good at English, and this is my first post. I usually post here in Japanese. Nice to meet you.

These are my solution.

$$$O(N^2)$$$

Tutorial says DP, and most Accepted programs are DP, too.

But, my program is greedy. Is greedy the correct way to solve it?

C++ 92 ms

$$$O(N \log N)$$$

use Lazy Segment Tree. If the above greedy is correct, then lazysegtree can be used.

C++ 62 ms