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




可复制的 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