2023-2024 ICPC, Swiss Subregional |
---|
Закончено |
We have a collection of problems, called a problem set. Each problem $$$P$$$ has its difficulty $$$d(P)$$$ and beauty $$$b(P)$$$.
A contest is an ordered set of problems selected from the problem set. The beauty of a contest is the sum of individual beauties of the problems it consists of.
Let $$$(P_1, P_2, \dots, P_k)$$$ be the problems in the contest. For a contest to be valid, each problem must be roughly twice as difficult as the one immediately preceding it, formally
$$$$$$\forall i \in \{2, \dots, k\}: d(P_{i-1}) = \left\lfloor \frac{d(P_i)}{2} \right\rfloor$$$$$$
Initially, the problem set is empty. You are given $$$n$$$ operations which modify the problem set. Each of these operations is described by a single line consisting of three integers, as follows:
After each operation, output the beauty of the most beautiful valid contest using some problems (possibly all or none) from the problem set.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of operations.
Each of the following $$$n$$$ lines consists of three space-separated integers $$$t_i$$$, $$$d_i$$$, $$$b_i$$$ ($$$1 \leq t_i \leq 2$$$, $$$1 \leq d_i \leq 10^6$$$, $$$-10^{17} \leq b_i \leq 10^{17}$$$) — the operation to be made, the problem difficulty and the problem beauty, respectively.
For each operation, output a single line with an integer: the beauty of the most beautiful contest given the current problem set.
101 1 101 2 101 3 201 4 201 5 202 3 202 2 102 4 202 5 202 1 10
10 20 30 40 40 40 20 20 10 0
11 10 -50
0
Название |
---|