/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は 10^{100} 個の植木鉢を持っています。最初、高橋君は植物を 1 個も育てていません。
Q 個のクエリが与えられるので、順に処理してください。
クエリは次の 3 種類です。
1: 植物が植えられていない植木鉢を 1 個用意し、その植木鉢に植物を植える。このとき植物の高さは 0 である。2 T: T 日待つ。このとき植えてあるすべての植物の高さが T 増加する。3 H: 高さが H 以上の植物をすべて収穫し、収穫した植物の数を出力する。収穫した植物は植木鉢から取り除かれる。
ただし、高橋君が 1 種類目と 3 種類目のクエリを行うとき、かかる時間は 0 であるとします。
制約
- 1 \leq Q \leq 2 \times 10^{5}
- 1 \leq T,H \leq 10^{9}
- 3 種類目のクエリが 1 つ以上存在する
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
各クエリは以下のいずれかの形式で与えられる。
1
2 T
3 H
出力
3 種類目のクエリが K 個あるとき、K 行出力せよ。 i 行目 (1\leq i\leq K) には、i 個目の 3 種類目のクエリに対する答えを出力せよ。
入力例 1
6 1 2 15 1 3 10 2 20 3 20
出力例 1
1 1
クエリは次の順で処理されます。
- 1 個目のクエリでは高さ 0 の植物が 1 個植えられます。
- 2 個目のクエリでは高さ 0 の植物が高さ 15 になります。
- 3 個目のクエリでは高さ 0 の植物が 1 個植えられます。このとき、高さ 0 と高さ 15 の植物が 1 個ずつあります。
- 4 個目のクエリでは高さ 10 以上の植物が収穫されます。このとき、高さ 15 の植物が 1 個収穫されて高さ 0 の植物が 1 個残ります。1 個の植物を収穫したため、1 行目に 1 と出力します。
- 5 個目のクエリでは高さ 0 の植物が高さ 20 になります。
- 6 個目のクエリでは高さ 20 以上の植物が収穫されます。このとき、高さ 20 の植物が 1 個収穫されます。よって、2 行目に 1 と出力します。
入力例 2
15 1 1 2 226069413 3 1 1 1 2 214168203 1 3 214168203 1 1 1 2 314506461 2 245642315 3 1
出力例 2
2 2 4
Score : 400 points
Problem Statement
Takahashi has 10^{100} flower pots. Initially, he is not growing any plants.
You are given Q queries to process in order.
There are three types of queries as follows.
1: Prepare one empty flower pot and put a plant in it. Here, the plant's height is 0.2 T: Wait for T days. During this time, the height of every existing plants increases by T.3 H: Harvest all plants with a height of at least H, and output the number of plants harvested. The harvested plants are removed from their flower pots.
Assume that performing queries of the first and third types takes zero time.
Constraints
- 1 \leq Q \leq 2 \times 10^{5}
- 1 \leq T,H \leq 10^{9}
- There is at least one query of the third type.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Each query is given in one of the following formats:
1
2 T
3 H
Output
Let there be K queries of the third type, and print K lines. The i-th line (1 \leq i \leq K) should contain the answer to the i-th query of type 3.
Sample Input 1
6 1 2 15 1 3 10 2 20 3 20
Sample Output 1
1 1
Queries are processed in the following order:
- In the first query, a plant of height 0 is planted.
- In the second query, the height of the plant increases to 15.
- In the third query, another plant of height 0 is planted. Now there is one plant of height 15 and one plant of height 0.
- In the fourth query, all plants with height at least 10 are harvested. Here, one plant of height 15 gets harvested, and one plant of height 0 remains. Since one plant was harvested, print 1 on the first line.
- In the fifth query, the height of the remaining plant increases to 20.
- In the sixth query, all plants with height at least 20 are harvested. Here, one plant of height 20 gets harvested. Thus, print 1 on the second line.
Sample Input 2
15 1 1 2 226069413 3 1 1 1 2 214168203 1 3 214168203 1 1 1 2 314506461 2 245642315 3 1
Sample Output 2
2 2 4