← 返回题目列表

AtCoder · joisc2018_f

F. 最差记者 3

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

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

最悪の記者 3 (Worst Reporter 3) - 原题 PDF 第 1 页
原题PDF第1页
最悪の記者 3 (Worst Reporter 3) - 原题 PDF 第 2 页
原题PDF第2页
最悪の記者 3 (Worst Reporter 3) - 原题 PDF 第 3 页
原题PDF第3页
最悪の記者 3 (Worst Reporter 3) - 原题 PDF 第 4 页
原始 PDF 第 4 部分
可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                  Contest Day 2 – Worst Reporter 3


           最悪の記者3 (Worst Reporter 3)



  IOI 2018 の開会式では,N 人の選手が一列に並んで行進する.選手が進む道は数直線としてあらわされ
る.選手たちは全員,数直線上の正の方向を向いて行進する.最初,前からi 番目(1 ≦i ≦N) の選手は,
座標−i に立っている.座標0 には,旗手のIOI ちゃんが立っている.
 すべての選手には呑気さという値が定まっている.前からi 番目の選手の呑気さはDi である.選手たち
は,常に,以下の規則で行動する.

   • 前からi 番目の選手は,自分の目の前の参加者(選手またはIOI ちゃん) との距離がDi + 1 以上離れ
   たなら,目の前の参加者から距離1 の位置まで進む.そうでないなら,動かない.

  IOI ちゃんは,単位時刻あたり1 だけ道の上を正の方向に進む.選手たちは全員,上記の条件が満たさ
れれば即座に進む.
 あなたは,開会式を取材しに来た記者である.あなたは写真を撮らなければならなかったが,開会式の
間中ずっと熟睡していた.仕方がないので,あなたは会場の写真を撮り,その写真に参加者の絵を描いて
誤魔化すことにした.
 誤魔化したことを明るみに出さないために,また絵を描く手間を見積もるために,あなたは以下のQ 個
の値を知っておきたい.

   • 時刻T j における,L j 以上R j 以下の座標に立っている参加者の人数(1 ≦j ≦Q)


課題

 各選手の呑気さと,Q 個の質問の情報が与えられるので,それぞれの質問ごとに,条件を満たす参加者
の人数を求めるプログラムを作成せよ.


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には,整数N, Q が空白を区切りとして書かれている.これらは順に,選手の人数と,質問の
   個数を表す.選手の人数にIOI ちゃんは含まれないことに注意せよ.

   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Di が書かれている.これらは順に,前からi 番目の
   選手の呑気さを表す.

   • 続くQ 行のうちのj 行目(1 ≦j ≦Q) には,整数T j, L j, R j が空白を区切りとして書かれている.こ
   れらはj 個目の質問の情報を表す.





                     最悪の記者3– 1 / 4

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                  Contest Day 2 – Worst Reporter 3


出力

 標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には,j 個目の質問の答えを表す整数を出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 1 ≦N ≦500 000.

   • 1 ≦Q ≦500 000.

   • 1 ≦Di ≦1 000 000 000 (1 ≦i ≦N).

   • 1 ≦T j ≦1 000 000 000 (1 ≦j ≦Q).

   • 1 ≦L j ≦R j ≦1 000 000 000 (1 ≦j ≦Q).


小課題

小課題1 [7 点]

   • Di = 1 (1 ≦i ≦N).


小課題2 [12 点]

 以下の条件を満たす.

   • N ≦1 000.

   • Q ≦1 000.

   • T j ≦1 000 (1 ≦j ≦Q).

   • 1 ≦Lj ≦R j ≦1 000 (1 ≦j ≦Q).


小課題3 [81 点]

 追加の制限はない.





                     最悪の記者3– 2 / 4

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                  Contest Day 2 – Worst Reporter 3


入出力例

  入力例1        出力例1
   3 6                  0
   2                    1
   5                    1
   3                    2
   1 2 4                1
   2 2 4                2
   3 2 4
   4 2 4
   5 2 4
   6 2 4

 この入力例では,選手とIOI ちゃんは以下のように進む.
 以下では,数直線上において,座標がL 以上R 以下の点の全体を区間[L, R] で表す.

   • 最初,IOI ちゃんは座標0 に,1, 2, 3 番目の選手は座標−1, −2, −3 にいる.

   • 時刻1 に,IOI ちゃんは座標1 に進む.進む選手はおらず,1, 2, 3 番目の選手は座標−1, −2, −3 にい
   る.区間[2, 4] には誰もいないので,1 個目の質問には0 を出力する.

   • 時刻2 に,IOI ちゃんは座標2 に進む.IOI ちゃんと1 番目の選手の間の距離が3 になったため,1
   番目の選手は座標1 に進む.1, 2, 3 番目の選手は座標1, −2, −3 にいる.区間[2, 4] にはIOI ちゃんの
   みがいるので,2 個目の質問には1 を出力する.

   • 時刻3 に,IOI ちゃんは座標3 に進む.進む選手はおらず,1, 2, 3 番目の選手は座標1, −2, −3 にいる.
    区間[2, 4] にはIOI ちゃんのみがいるので,3 個目の質問には1 を出力する.

   • 時刻4 に,IOI ちゃんは座標4 に進む.IOI ちゃんと1 番目の選手の間の距離が3 になったため,1
   番目の選手は座標3 に進む.1, 2, 3 番目の選手は座標3, −2, −3 にいる.区間[2, 4] にはIOI ちゃんと
     1 番目の選手がいるので,4 個目の質問には2 を出力する.

   • 時刻5 に,IOI ちゃんは座標5 に進む.進む選手はおらず,1, 2, 3 番目の選手は座標3, −2, −3 にいる.
    区間[2, 4] には1 番目の選手のみがいるので,5 個目の質問には1 を出力する.

   • 時刻6 に,IOI ちゃんは座標6 に進む.IOI ちゃんと1 番目の選手の間の距離が3 になったため,1
   番目の選手は座標5 に進む.さらに,1 番目の選手と2 番目の選手の間の距離が7 になったため,2
   番目の選手は座標4 に進む.さらに,2 番目の選手と3 番目の選手の間の距離が7 になったため,3
   番目の選手は座標3 に進む.1, 2, 3 番目の選手は座標5, 4, 3 にいる.区間[2, 4] には2 番目の選手と
     3 番目の選手がいるので,6 個目の質問には2 を出力する.





                     最悪の記者3– 3 / 4

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                         Spring Training Camp/Qualifying Trial
                                            March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                Contest Day 2 – Worst Reporter 3



 入力例2        出力例2
 4 2                  2
 1                    0
 1
 1
 1
 2 1 4
 1 3 6

この入力例は,小課題1 の条件を満たす.



 入力例3        出力例3
 6 6                  1
 11                   6
 36                   0
 28                   5
 80                   2
 98                   7
 66
 36 29 33
 190 171 210
 18 20 100
 1000 900 1100
 92 87 99
 200 100 300





                    最悪の記者3– 4 / 4