Sasha and a Patient Friend
Contest: Codeforces Round 539 (Div. 1)
Difficulty rating: 2800
Tags: binary search, data structures, implementation

Fedya and Sasha are friends, that's why Sasha knows everything about Fedya.

Fedya keeps his patience in an infinitely large bowl. But, unlike the bowl, Fedya's patience isn't infinite, that is why let $$$v$$$ be the number of liters of Fedya's patience, and, as soon as $$$v$$$ becomes equal to $$$0$$$, the bowl will burst immediately. There is one tap in the bowl which pumps $$$s$$$ liters of patience per second. Notice that $$$s$$$ can be negative, in that case, the tap pumps out the patience. Sasha can do different things, so he is able to change the tap's speed. All actions that Sasha does can be represented as $$$q$$$ queries. There are three types of queries:

1. "1 t s"  — add a new event, means that starting from the $$$t$$$-th second the tap's speed will be equal to $$$s$$$.
2. "2 t"  — delete the event which happens at the $$$t$$$-th second. It is guaranteed that such event exists.
3. "3 l r v" — Sasha wonders: if you take all the events for which $$$l \le t \le r$$$ and simulate changes of Fedya's patience from the very beginning of the $$$l$$$-th second till the very beginning of the $$$r$$$-th second inclusive (the initial volume of patience, at the beginning of the $$$l$$$-th second, equals to $$$v$$$ liters) then when will be the moment when the bowl will burst. If that does not happen, then the answer will be $$$-1$$$.

Since Sasha does not want to check what will happen when Fedya's patience ends, and he has already come up with the queries, he is asking you to help him and find the answer for each query of the $$$3$$$-rd type.

It is guaranteed that at any moment of time, there won't be two events which happen at the same second.

Input format:
The first line contans one integer $$$q$$$ ($$$1 \le q \le 10^5$$$)  — the number of queries.

Each of the next $$$q$$$ lines have one of the following formats:

- 1 t s ($$$1 \le t \le 10^9$$$, $$$-10^9 \le s \le 10^9$$$), means that a new event is added, which means that starting from the $$$t$$$-th second the tap's speed will be equal to $$$s$$$.
- 2 t ($$$1 \le t \le 10^9$$$), means that the event which happens at the $$$t$$$-th second must be deleted. Guaranteed that such exists.
- 3 l r v ($$$1 \le l \le r \le 10^9$$$, $$$0 \le v \le 10^9$$$), means that you should simulate the process from the very beginning of the $$$l$$$-th second till the very beginning of the $$$r$$$-th second inclusive, and to say when will the bowl burst.

It is guaranteed that $$$t$$$, $$$s$$$, $$$l$$$, $$$r$$$, $$$v$$$ in all the queries are integers.

Also, it is guaranteed that there is at least one query of the $$$3$$$-rd type, and there won't be a query of the $$$1$$$-st type with such $$$t$$$, that there already exists an event which happens at that second $$$t$$$.

Output format:
For each query of the $$$3$$$-rd type, print in a new line the moment when the bowl will burst or print $$$-1$$$ if it won't happen.

Your answer will be considered correct if it's absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first example all the queries of the $$$3$$$-rd type cover all the events, it's simulation is following:

Example input:
6
1 2 1
1 4 -3
3 1 6 1
3 1 6 3
3 1 6 4
3 1 6 5

Example output:
5
5.666667
6
-1

Example input:
10
1 2 2
1 4 4
1 7 -10
3 2 4 1
3 5 6 0
3 1 15 1
2 4
3 1 15 1
1 8 1
3 1 15 1

Example output:
-1
5
8.7
8.1
-1

Editorial:
Let's keep not deleted pairs ($$$t, s$$$) in a treap where $$$t$$$ will be the key of some node.
Also we need some auxiliary variables. So each node in the treap will store that:
• $$$time$$$  — time of the event
• $$$speed$$$  — speed of the tap since second $$$time$$$
• $$$tL$$$, $$$tR$$$  — the minimum and the maximum $$$time$$$ in the subtree of that node
• $$$speedR$$$  — the $$$speed$$$ of the event with maximum $$$time$$$ in the subtree of that node
• $$$res$$$  — the value of patience after processing all events from the subtree (we assume that the value before $$$tL$$$-th second is $$$0$$$)
• $$$mn$$$  — what is the minumum value of patience if we process all events from the subtree (also initial value is $$$0$$$)
• links to the left child and to the right child
It turns out that this information is enough. Now to make treap work correctly it should be possible to merge two chilrens of some node. Let's look how to do it (suppose that this node has either left child ($$$LC$$$) or right child ($$$RC$$$)):
• $$$time$$$ doesn't change
• $$$speed$$$ doesn't change
• $$$tL = LC.tL$$$, $$$tR = RC.tR$$$, $$$speedR = RC.speedR$$$
• It is easier to calculate $$$res$$$ and $$$mn$$$ simulatenously. Look at this block of code: mn = 0, res = 0  mn = min(mn, LC.mn)  res += LC.res + LC.speedR * (time - LC.tR)  mn = min(mn, res)  res += speed * (RC.tL - time)  mn = min(mn, res + RC.mn)  res += RC.res  mn = min(mn, res)   It goes through all possible periods of time where $$$mn$$$ can be, and finds the best one, during this it calculates $$$res$$$.
If there is no left or right child then the calculation doen't change too much.
So if you have combine function then you can do insert, delete, split, merge.
You can answer queries of the $$$3$$$-rd type in the following way. Cut out the needed range from the treap. And go down the treap starting from the root while you can (you go to the left child, if the value of patience becomes equal to $$$0$$$ earlier than $$$time$$$, you can check that using the imformation stored in nodes, then check the right one if it is needed). So it is left to consider some extreme cases, which I leave you as and exercise, and that is all.
The complexity is $$$O(q \cdot log(q))$$$. If you don't like treaps, you can actually use segment tree on pointers, or make coordinate compression and write a simple segment tree, the complexity will stay the same.