← 返回题目列表

AtCoder · joisc2019_i

I. 穿越时空的Bitaro

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

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

時をかけるビ太郎 (Bitaro, who Leaps through Time) - 原题 PDF 第 1 页
原题PDF第1页
時をかけるビ太郎 (Bitaro, who Leaps through Time) - 原题 PDF 第 2 页
原题PDF第2页
時をかけるビ太郎 (Bitaro, who Leaps through Time) - 原题 PDF 第 3 页
原题PDF第3页
時をかけるビ太郎 (Bitaro, who Leaps through Time) - 原题 PDF 第 4 页
原题PDF第4页
時をかけるビ太郎 (Bitaro, who Leaps through Time) - 原题 PDF 第 5 页
原题PDF第5页
可复制的 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