以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。





可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Ants and Sugar
蟻と角砂糖(Ants and Sugar)
生物学者のJOI 君は,蟻と角砂糖を使った実験を計画している.
JOI 君の実験は,左右に横たわる長さ1 000 000 000 (= 109) の細長いまっすぐな棒の上で行われる.棒の
左端から右方向に距離x 進んだ点を,座標x の点と呼ぶことにする.
現在,棒の上には何も存在しない.これからJOI 君は,Q 回の操作を行う.i 回目(1 ≦i ≦Q) の操作は3
つの整数Ti, Xi, Ai で表され,以下の操作を行うことを意味する.
• Ti = 1 のとき:JOI 君が座標Xi の点にAi 匹の蟻を置く.
• Ti = 2 のとき:JOI 君が座標Xi の点にAi 個の角砂糖を置く.
なお,蟻や角砂糖は非常に小さいため,同じ座標にそれらが複数個存在することは可能である.また,同じ
座標に対して複数回操作することもありうる.
ところで,実験で使う蟻には不思議な特性がある.具体的には,JOI 君が手を叩くと,それぞれの蟻は以
下の動作を一度だけ行う.
• 自分との距離がL 以下の角砂糖が存在するなら,その中から1 つを自由に選び,それを食べる.
なお,複数の蟻が同じ1 つの角砂糖を食べることもありうる.
JOI 君は,すべてのk (1 ≦k ≦Q) について,以下の質問の答えを知りたい.
• k 回目の操作が終わった段階で手を叩いた場合,最大で何個の角砂糖が1 匹以上の蟻に食べられるか.
JOI 君が行う操作の情報およびL の値が与えられるので,すべてのk についてJOI 君の質問に答えるプロ
グラムを作成せよ.
なお,実際には操作の途中で手を叩くことはないため,蟻の位置は操作の間で変化せず,また角砂糖が食
べられることもない.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
Q L
T1 X1 A1
T2 X2 A2
...
TQ XQ AQ
蟻と角砂糖– 1 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Ants and Sugar
出力
標準出力にQ 行で出力せよ.k 行目(1 ≦k ≦Q) には,k 回目の操作が終わった段階で手を叩いた場合,
最大で何個の角砂糖が1 匹以上の蟻に食べられるかを出力せよ.
制約
• 1 ≦Q ≦500 000.
• 1 ≦L ≦1 000 000 000 (= 109).
• Ti は1 または2 である(1 ≦i ≦Q).
• 0 ≦Xi ≦1 000 000 000 (= 109) (1 ≦i ≦Q).
• 1 ≦Ai ≦1 000 000 000 (= 109) (1 ≦i ≦Q).
小課題
1. (6 点) Q ≦3 000.
2. (16 点) L = 1,Xi ≦Q −1,Xi + Ti は偶数(1 ≦i ≦Q).
3. (26 点) Q は偶数,Ti = 1 (1 ≦i ≦Q/2),Ti = 2 (Q/2 + 1 ≦i ≦Q).
4. (52 点) 追加の制約はない.
入出力例
入力例1 出力例1
4 1 0
1 1 1 1
2 2 1 1
1 3 1 2
2 0 1
この入力例では,一連の操作の内容,およびそれぞれのk に対する質問の答えは以下のようになる.
1. 座標1 に1 匹の蟻を置く.
この時点で手を叩いた場合,角砂糖は存在しないため,k = 1 の場合の質問の答えは0 になる.
2. 座標2 に1 個の角砂糖を置く.
蟻と角砂糖– 2 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Ants and Sugar
この時点で手を叩いた場合,座標1 の蟻が座標2 の角砂糖を食べるため,k = 2 の場合の質問の答え
は1 になる.
3. 座標3 に1 匹の蟻を置く.
この時点で手を叩いた場合,座標1, 3 の蟻は両方とも座標2 の角砂糖を食べるため,k = 3 の場合の
質問の答えは1 になる.
4. 座標0 に1 個の角砂糖を置く.
この時点で手を叩いた場合,座標1 の蟻が座標0 の角砂糖を,座標3 の蟻が座標2 の角砂糖を食べ
るときに,食べられる角砂糖の個数が最大となる.よって,k = 4 の場合の質問の答えは2 になる.
この入力例は小課題1, 2, 4 の制約を満たす.
入力例2 出力例2
20 1 0
2 16 778913911 0
1 7 558407445 0
1 1 589762439 74646747
1 17 74646747 74646747
1 1 149104909 778913911
1 15 956697952 1168286902
2 6 389372991 1168286902
2 4 867453845 1168286902
1 15 157353445 1168286902
1 9 846177695 1168286902
1 7 747107163 1693957364
2 10 525670462 2103741597
2 16 478912944 2405475358
2 6 301733761 2405475358
2 12 132966485 2405475358
1 1 748012313 2725982591
2 10 830922632 2725982591
1 19 969484637 2858949076
1 13 370330582 2858949076
1 1 464798040
この入力例は小課題1, 2, 4 の制約を満たす.
蟻と角砂糖– 3 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Ants and Sugar
入力例3 出力例3
20 6 0
2 27 12 0
2 9 11 0
1 36 10 4
2 39 4 4
2 14 9 10
2 33 7 10
2 38 20 10
2 0 20 10
2 25 16 13
1 14 3 30
1 13 19 30
2 6 4 32
2 15 6 32
2 33 4 40
1 12 11 41
1 44 1 44
2 17 14 44
2 12 19 44
1 48 18 44
2 30 16
この入力例は小課題1, 4 の制約を満たす.
蟻と角砂糖– 4 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Ants and Sugar
入力例4 出力例4
20 268886972 0
1 984472666 733463744 0
1 478477245 94817772 0
1 242536956 330762563 0
1 65794782 319137646 0
1 320548477 937296140 0
1 815011370 938193848 0
1 565184190 917533785 0
1 245417414 534089975 0
1 529908772 977043962 0
1 603891865 700935654 479827216
2 167042244 479827216 1278170671
2 173921297 798343455 2088297397
2 916159596 810126726 2553832704
2 999299355 465535307 2949828263
2 965968070 501768990 2949828263
2 936073643 174976034 3727900335
2 832859952 778072072 3727900335
2 955489596 704853861 4110329327
2 246733786 382428992 4501234333
2 227669861 390905006
この入力例は小課題1, 3, 4 の制約を満たす.
蟻と角砂糖– 5 / 5