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





可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 3 – Harvest
収穫(Harvest)
IOI 農園は大きな湖の周りにあることで有名なりんご農園である.
IOI 農園にはN 人の従業員が雇われており,それぞれ1 からN までの番号が付けられている.また,IOI
農園ではM 本のりんごの木が生えており,それぞれ1 からM までの番号が付けられている.湖の周りの
長さはL メートルである.
最初,従業員i (1 ≦i ≦N) は湖の最北端から湖の周りに沿って時計回りにAi メートルだけ進んだ地点で
待機している.Ai (1 ≦i ≦N) の値はすべて異なる.また,りんごの木j (1 ≦j ≦M) は湖の最北端から湖の
周りに沿って時計回りにBj メートルだけ進んだ地点に生えている.Bj (1 ≦j ≦M) の値はすべて異なる.
また,従業員の最初の待機場所にはりんごの木はない.
IOI 農園で育てられているりんごは特別な品種改良の結果,1 本の木に対して1 個のりんごしか実らない
が,収穫してからちょうどC 秒後に新たなりんごが実る.時刻0 ではすべてのりんごの木でりんごが実っ
ており,従業員たちは時刻0 に湖の周りを時計回りに秒速1 メートルで歩き始める.従業員がりんごの木
がある地点に到着してりんごが実っている場合,必ずりんごを収穫する(従業員がりんごの木がある地点に
到着したと同時に新たなりんごが実った場合も,そのりんごを収穫する).また,従業員がりんごを収穫す
るのにかかる時間は無視できるものとする.
IOI 農園の株主であるK 理事長は,経営者であるあなたに従業員の作業効率に関する報告書を提出するよ
う要求した.具体的には以下のQ 個の値を知る必要がある.
従業員Vk が時刻Tk までに収穫する(時刻Tk ちょうどに収穫する場合を含む) りんごの個数
(1 ≦k ≦Q).
従業員の人数,りんごの木の本数,湖の長さ,りんごを収穫してから新たに実るまでの時間,従業員とり
んごの木の位置,Q 個の質問の情報が与えられたとき,それぞれの質問ごとに収穫するりんごの個数を求め
るプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
収穫– 1 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 3 – Harvest
N M L C
A1 · · · AN
B1 · · · BM
Q
V1 T1
...
VQ TQ
出力
標準出力にQ 行で出力せよ.k 行目(1 ≦k ≦Q) には,k 個目の質問の答えを表す整数を出力せよ.
制約
• 1 ≦N ≦200 000.
• 1 ≦M ≦200 000.
• N + M ≦L ≦1 000 000 000.
• 1 ≦C ≦1 000 000 000.
• 0 ≦Ai < L (1 ≦i ≦N).
• Ai < Ai+1 (1 ≦i ≦N −1).
• 0 ≦Bj < L (1 ≦j ≦M).
• Bj < Bj+1 (1 ≦j ≦M −1).
• Ai , Bj (1 ≦i ≦N, 1 ≦j ≦M).
• 1 ≦Q ≦200 000.
• 1 ≦Vk ≦N (1 ≦k ≦Q).
• 1 ≦Tk ≦1 000 000 000 000 000 000 = 1018 (1 ≦k ≦Q).
小課題
1. (5 点) N ≦3 000,M ≦3 000,Q ≦3 000.
2. (20 点) Tk ≧1 000 000 000 000 000 = 1015 (1 ≦k ≦Q).
3. (75 点) 追加の制約はない.
収穫– 2 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 3 – Harvest
入出力例
入力例1 出力例1
3 2 7 3 2
1 4 6 1
0 5 1
3
1 7
2 3
3 8
• 時刻1 に従業員2 がりんごの木2 に実っているりんごを収穫し,従業員3 がりんごの木1 に実って
いるりんごを収穫する.
• 時刻3 に従業員2 がりんごの木1 の位置に到着するが,りんごは実っていないので収穫しない.
• 時刻4 に従業員1 がりんごの木2 に実っているりんごを収穫する.
• 時刻6 に従業員1 がりんごの木1 に実っているりんごを収穫する.従業員3 がりんごの木2 の位置
に到着するが,りんごは実っていないので収穫しない.
• 時刻8 に従業員2 がりんごの木2 に実っているりんごを収穫する.従業員3 がりんごの木1 の位置
に到着するが,りんごは実っていないので収穫しない.
従業員1 が時刻7 までに収穫する(時刻7 ちょうどに収穫する場合を含む) りんごの個数は2 個であるか
ら,1 行目に2 を出力する.
収穫– 3 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 3 – Harvest
入力例2 出力例2
5 3 20 6 146
0 4 8 12 16 7035
2 11 14 7
9 7359360
4 1932 202
2 93787 10320
1 89 0
5 98124798 628
1 2684 18
1 137598
3 2
3 8375
4 237
収穫– 4 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 3 – Harvest
入力例3 出力例3
8 15 217 33608 33230868503053
0 12 71 96 111 128 152 206 3
4 34 42 67 76 81 85 104 110 117 122 148 166 170 212 5
14 1
2 223544052420046341 123542793648997
3 86357593875941375 8
4 892813012303440034 165811220737767
1 517156961659770735 8
7 415536186438473633 7
6 322175014520330760 1
7 557706040951533058 1
6 640041274241532527 7
5 286263974600593111 7535161012043
8 349405886653104871 132506837660717
1 987277313830536091
5 989137777159975413
2 50689028127994215
7 445686748471896881
収穫– 5 / 5