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





可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro, who Leaps through Time
時をかけるビ太郎(Bitaro, who Leaps through Time)
ビーバーランドはN 個の都市からなり,都市には順に1 からN の番号が付いている.都市と都市を結ぶ
道はN −1 個あり,i 番目(1 ≦i ≦N −1) の道は都市i と都市i + 1 を双方向に結んでいる.また,ビーバー
ランドの1 日は1 000 000 000 個の単位時間に分割されており,単位としてビョウを用いている.1 日の始
まりからx ビョウ(0 ≦x < 1 000 000 000) 経過した時点を時刻x とする.どの道を通るにもちょうど1 ビョ
ウかかり,i 番目の道は時刻Li から時刻Ri までの間しか通ることができない.つまり,i 番目の道を通るに
は,Li ≦x ≦Ri −1 を満たす時刻x に都市i と都市i + 1 のいずれかから出発し,時刻x + 1 にもう一方の都
市に到着する必要がある.
ビーバーのビ太郎はビーバーランドに住むごく普通のビーバーである.いや,であったというのが正しい
であろうか.度重なる遅刻を改善しようと試みた結果,ビ太郎は時をさかのぼることができるようになって
しまったのである.この能力を1 回用いるとビ太郎は1 ビョウだけ時をさかのぼることができる.ただし,
この能力を用いても日をさかのぼることはできず,時刻0 から時刻1 までの間に能力を用いても同じ日の
時刻0 までしか戻ることができない.この能力はビ太郎が都市にいるときのみ用いる.また,この能力を用
いてもビ太郎の位置は変化しない.
しかし能力を使いすぎたビ太郎は,反動からか,体力をかなり消耗してしまった.反省したビ太郎は,で
きるだけ能力を使わずに移動する方法を見つけるため,Q ステップからなる思考実験を行うことにした.こ
の思考実験において,j ステップ目(1 ≦j ≦Q) では以下のいずれかを行う.
• Pj 番目の道を通ることができる時刻の区間を,時刻S j から時刻E j までに変更する.
• 都市Aj に時刻Bj の時点でいると仮定する.このとき,都市C j に同じ日の時刻D j の時点でいるた
めには,少なくとも何回能力を使う必要があるかを求める.
果たして思考実験の結果はどうなるであろうか.
ビーバーランドの都市の個数,道の情報,思考実験の内容が与えられたとき,思考実験の結果を求めるプ
ログラムを作成せよ.
時をかけるビ太郎– 1 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro, who Leaps through Time
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
N Q
L1 R1
...
LN−1 RN−1
(Query 1)
...
(Query Q)
ただし,各(Query j) (1 ≦j ≦Q) には4 個または5 個の整数が空白を区切りとして書かれている.1 個目
の整数をT j とすると,この行の内容は以下のいずれかである.
• T j = 1 のとき.この行には4 個の整数T j, Pj, S j, E j がこの順に書かれている.これは思考実験のj
ステップ目において,Pj 番目の道を通ることができる時刻の区間を時刻S j から時刻E j までに変更
することを表す.
• T j = 2 のとき.この行には5 個の整数T j, Aj, Bj, C j, Dj がこの順に書かれている.これは思考実験
のj ステップ目において,都市Aj に時刻Bj の時点でいると仮定したとき,都市C j に同じ日の時刻
Dj の時点でいるためには,少なくとも何回能力を使う必要があるかを求めることを表す.
出力
標準出力に,T j = 2 となるステップのそれぞれに対して,使う能力の回数の最小値を順に1 行ずつ出力
せよ.
時をかけるビ太郎– 2 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro, who Leaps through Time
制約
• 1 ≦N ≦300 000.
• 1 ≦Q ≦300 000.
• 0 ≦Li < Ri ≦999 999 999 (1 ≦i ≦N −1).
• 1 ≦T j ≦2 (1 ≦j ≦Q).
• 1 ≦P j ≦N −1 (1 ≦j ≦Q,T j = 1).
• 0 ≦S j < E j ≦999 999 999 (1 ≦j ≦Q,T j = 1).
• 1 ≦A j ≦N (1 ≦j ≦Q,T j = 2).
• 0 ≦Bj ≦999 999 999 (1 ≦j ≦Q,T j = 2).
• 1 ≦C j ≦N (1 ≦j ≦Q,T j = 2).
• 0 ≦Dj ≦999 999 999 (1 ≦j ≦Q,T j = 2).
小課題
1. (4 点) N ≦1000,Q ≦1000.
2. (30 点) T j = 2 (1 ≦j ≦Q).
3. (66 点) 追加の制約はない.
時をかけるビ太郎– 3 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro, who Leaps through Time
入出力例
入力例1 出力例1
3 3 2
0 5 4
0 5
2 1 3 3 3
1 2 0 1
2 1 3 3 3
思考実験の1 ステップ目では,都市1 から都市2 に1 ビョウかけて移動し,都市2 から都市3 に1 ビョ
ウかけて移動することで,都市3 に時刻5 に到着することができる.よって,その後2 回能力を使うこと
で都市3 に時刻3 の時点でいることができる.
思考実験の2 ステップ目では,2 番目の道を通ることができる時刻の区間を,時刻0 から時刻1 までに変
更する.
思考実験の3 ステップ目では,都市1 から都市2 に1 ビョウかけて移動することで,都市2 に時刻4 の
時点でいることができる.よって,その後4 回能力を使ったあと,都市3 に1 ビョウかけて移動し,2 ビョ
ウ待つことで,都市3 に時刻3 の時点でいることができる.
入力例2 出力例2
5 5 4
3 5 3
4 8 2
2 6 3
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 4 5 1 5
時をかけるビ太郎– 4 / 5
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Bitaro, who Leaps through Time
入力例3 出力例3
7 7 145611455
112103440 659752416 0
86280800 902409187 447180143
104535475 965602300 0
198700180 945132880 207252171
137957976 501365807 0
257419446 565237610 0
2 4 646977260 7 915994878
2 1 221570340 6 606208433
2 7 948545948 4 604273995
2 7 247791098 5 944822313
2 7 250362511 2 50167280
2 3 364109400 4 555412865
2 7 33882587 7 186961394
入力例4 出力例4
7 7 10467449
535825574 705426142 164858601
964175291 996597835
481817391 649559926
4519006 410772613
74521477 274584126
256535565 899389890
1 6 511428966 602601933
1 1 69986642 201421232
2 3 636443425 4 625975977
1 6 235225515 405336399
2 3 866680458 3 701821857
1 6 180606048 900533151
1 6 612564160 720179605
時をかけるビ太郎– 5 / 5