WARNING: DISGUSTING PROBLEM ALERT
At the start of the year, I wrote a very painful implementation problem. My official solution was over 200 lines long and I was wondering if anyone could come up with a more elegant solution.
The problem is as follows:
Problem
Given some subtasks, the highest score was 72 by A_Wallaby. Majority of participants scored 27 points, where $$$B_i = 0$$$ for all $$$i$$$.
Solution
This problem is by no measure an elegant problem. It took me close to 4h to implement. I was wondering if anyone could find a more elegant solution? If anyone is interested, here is the problem statement and the solution code.
Auto comment: topic has been updated by dvdg6566 (previous revision, new revision, compare).
I'm not sure if this would be much easier than your original solution, but if you can afford $$$O(N log^2(N))$$$ complexity, I would go for the following idea:
Let's consider (offline) Divide & Conquer (it can also be done online, but whatever). This effectively lets us reduce our problem to the problem of computing the contribution of ranges that contain a given vertical separator M
Now, for a given range, we have a picture like the one above. It is relatively straightforward to notice that you can convert the updates in the input to $$$O(N log(N))$$$ (in total, over all D&C ranges) primitive updates of form:
You can guarantee yourself by the way you produce the primitive updates that the monotonicity that you see in the above picture is valid throughout the whole process.
Now, what remains to do is how to simulate these updates. Let's suppose we want to erase a red box. What changes is the contribution of the red box immediately to its right (it's easy to see how that changes), and the contributions of all blue boxes that point to the (to be erased) box (blue arrows, in the picture). Insertion is similar, although in this case you need to "split" the blue boxes pointing to a red box to the left of yours into two sets.
Both insert and erase can be supported if we keep a segment tree (with lazy propagation) over the blue pointers, and we recurse downwards (in a brute-force fashion) if in our current segment tree node there are two values pointing to two different red boxes. Think of Segment Tree Beats, it's the same basic principle.
In the end it might not be much simpler, but at least in my head it's a quite clean solution.
Follow-up: I think this solution can be adapted to be solved in $$$O(N log N)$$$ (perhaps replacing the segment tree with a simpler data structure like doubly-linked list), but I'm not exactly sure how it would work out.
Now that I think about it, it can be done a lot easier if you keep a segment tree over the union (interweave) of the blue boxes and the red boxes in the sorted order. This way, each update can be done with just one pass over the segment tree.
More specifically, one update (insert/erase) on a red box would affect the contiguous range of boxes starting from the previous red box in the set to the current red box in the set.
hmm I haven't really have had the chance to verify, but this is an interesting solution that I think has a good chance of working. Thanks for the idea!
Thanks for the idea of D&C across on vertical separator $$$M$$$! Building on your idea, I managed to find a solution that runs in $$$O(Nlog^2N)$$$*. The code is here: https://pastebin.pl/view/c638f4cd
Basically, when processing a range $$$[L,R]$$$, we want to compute for each time from $$$L-1$$$ (none updated) to $$$R$$$ (all updated), what is the sum of rangemax across all ranges that pass through $$$M$$$?
We can process the times from $$$L-1$$$ to $$$M$$$ and $$$M+1$$$ to $$$R$$$ separately. There will be an updated side and a static side. We can use a monotonic stack on the updated side and use binary search on the static side to update the sum. (I'm leaving out alot of details here cause I don't really feel like explaining in much detail, I'm sorry).
*While there are solutions that run in $$$O(NlogN)$$$, my $$$O(Nlog^2N)$$$ seems to run at least twice as fast as any $$$O(NlogN)$$$ solutions that I've seen on the judge. I guess it's cause lazy propagation segment trees are slow and dnc are bsta are both fast.
Anywhere we can submit?
Maybe here but have to register first : https://dunjudge.me/analysis/problems/2048/
just a warning, the judge is quite unstable. If you get a 502 when u open it i guess you just have to wait.