P6619 [NOI Qualifier Joint Contest 2020 A/B] Ice and Fire Warriors

A Volume D1T1, B Volume D1T3. Time limit: 3 s, memory limit: 512 MB.

A match is about to begin. Each warrior has two attributes: temperature and energy. There are two factions of warriors. Ice warriors’ skills cool the surroundings and deal freezing damage, so the arena temperature must be no lower than the warrior’s own temperature for them to participate. Fire warriors’ skills heat the surroundings and deal burning damage, so the arena temperature must be no higher than the warrior’s own temperature for them to participate. Once the arena temperature is fixed, the warriors who can participate on each side form a queue. Ice warriors are sorted by their own temperature from low to high, and fire warriors are sorted by their own temperature from high to low. If temperatures are equal, the warrior with higher energy goes first. First, the first warriors of both sides fight. They consume the same amount of energy; the warrior with less energy will run out of energy and leave the match, while the warrior with remaining energy continues to fight the next warrior on the other side (if both run out of energy, then the next warriors on both sides fight). This repeats until one side’s queue becomes empty, and the match ends. You need to find the best arena temperature: the maximum temperature value among those that make the total energy consumed by both sides as large as possible. Now, the match is still in the registration stage, and currently no warriors have registered. Next, you will continuously receive registration messages and withdrawal messages. A registration message contains the faction and the two attributes of the registering warrior, and a withdrawal message contains the index of the registration message to withdraw. Every time the registration status changes (i.e., you receive one message), you must immediately report the current best arena temperature, and the sum of the total energy consumed by both sides at that temperature. If under the current situation the match cannot be held at any temperature (i.e., one side has no warrior that can participate), output `Peace`.

The first line contains an integer $Q$, the number of messages. The next $Q$ lines are either `1 t x y` $(t \in \{0, 1\}$, and $x$ and $y$ are both positive integers$)$ or `2 k` ($k$ is a positive integer): `1 t x y` denotes a registration message. If $t = 0$, the registering warrior is an ice warrior; if $t = 1$, the registering warrior is a fire warrior. $x$ is the warrior’s own temperature, and $y$ is the warrior’s energy. `2 k` denotes a withdrawal message, withdrawing the $k$-th message. The withdrawn message is guaranteed to be a registration message. A withdrawn message will not be withdrawn again.

Output $Q$ lines. Each line contains two positive integers separated by one space, representing the current best temperature and the sum of the total energy consumed by both sides at that temperature.

#### Sample 1 Explanation For convenience, assume that if the $k$-th message is a registration message, then the corresponding warrior is warrior $k$. In the sample, warriors $1,2,3,4,6,7,8$ exist. Since the 5-th message is a withdrawal message, there is no warrior $5$. The outputs are explained one by one below: 1. Only fire warriors exist: warrior $1$. The match cannot be held, output `Peace`. 2. Temperatures $100 \sim 103$ can all achieve the maximum consumed energy $200$: warrior $1$ vs warrior $2$ consumes energy $200$, so the best temperature is $103$. 3. Temperatures $100 \sim 103$ can all achieve the maximum consumed energy $200$: warrior $1$ vs warrior $2$ consumes energy $200$, so the best temperature is $103$. 4. Temperature $103$ can achieve the maximum consumed energy $300$: first, warrior $1$ vs warrior $2$ consumes energy $200$; then, warrior $1$ vs warrior $4$ consumes energy $100$, so the best temperature is $103$. 5. From now on, warrior $1$ no longer exists. Temperatures $100 \sim 102$ can achieve the maximum consumed energy $200$: warrior $2$ vs warrior $3$ consumes energy $200$, so the best temperature is $102$. #### Sample 2 See the additional files `icefire2.in` and `icefire2.ans`. #### Constraints $10\%$ of the data: $Q \leq 100$, $x \leq 10^3$. Another $20\%$ of the data: $Q \leq 10^4$, $x \leq 5000$, there are no withdrawal messages, and the input $x$ is non-decreasing in order. $60\%$ of the data (including the above $20\%$, same below): $Q \leq 2 \times 10^5$, $x \leq 2 \times 10^5$. $90\%$ of the data: $Q \leq 2 \times 10^6$, $x \leq 2 \times 10^6$. $100\%$ of the data: $1 \leq Q \leq 2 \times 10^6$, $1 \leq x \leq 2 \times 10^9$, the sum of all $y$ does not exceed $2 \times 10^9$, and it is guaranteed that there do not exist two warriors with exactly the same $t, x, y$. Translated by ChatGPT 5