← 返回题目列表

AtCoder · joisc2022_i

I. 蚂蚁和糖

中文机器翻译题面 查看原题

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

蟻と角砂糖 (Ants and Sugar) - 原题 PDF 第 1 页
原题PDF第1页
蟻と角砂糖 (Ants and Sugar) - 原题 PDF 第 2 页
原题PDF第2页
蟻と角砂糖 (Ants and Sugar) - 原题 PDF 第 3 页
原题PDF第3页
蟻と角砂糖 (Ants and Sugar) - 原题 PDF 第 4 页
原题PDF第4页
蟻と角砂糖 (Ants and Sugar) - 原题 PDF 第 5 页
原题PDF第5页
可复制的 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