← 返回题目列表

AtCoder · joisc2017_b

B. 港口设施

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

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

港湾設備 (Port Facility) - 原题 PDF 第 1 页
原题PDF第4页
港湾設備 (Port Facility) - 原题 PDF 第 2 页
原题PDF第5页
港湾設備 (Port Facility) - 原题 PDF 第 3 页
原题PDF第6页
可复制的 PDF 提取文本
The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2017 (Komaba/Yoyogi, Tokyo)

                                                                      Contest Day 1 – Port Facility


                 港湾設備(Port Facility)



  JOI 港には毎日たくさんのコンテナが船で運ばれてきて,全国各地へとトラックで運ばれていく.
  JOI 港は非常に狭く,コンテナを積んでおける区画が2 つしかない.それぞれの区画には,コンテナを
縦にいくらでも積んでおくことができる.
 作業の安全のため,船で運ばれてきたコンテナは,どちらかの区画に積まなければならない.その区画
にすでにコンテナが積まれている場合は,すでに積まれているコンテナの一番上に積まなければならない.
トラックで運ぶときは,どちらかの区画に積まれたコンテナの一番上から順番に運んでいかなければなら
ない.
 本日,JOI 港には,N 個のコンテナが船で運ばれてくる予定である.そのすべての荷物が本日中にトラッ
クで運ばれていく.
 あなたはJOI 港の港湾設備の管理を任されており,すべてのコンテナが船で運ばれてくる時刻と,トラッ
クで運ばれていく時刻を知っている.コンテナを積み降ろしする方法は何通りあるかを1 000 000 007 で割っ
た余りを求めるプログラムを作成せよ.


課題

  JOI 港に運ばれてくるコンテナの個数と,それぞれのコンテナの運ばれてくる時刻と運ばれていく時刻
が与えられたとき,コンテナを積み降ろしする方法は何通りあるかを1 000 000 007 で割った余りを求める
プログラムを作成せよ.


入力

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

   • 1 行目には,整数N が書かれており,JOI 港に船で運ばれてくるコンテナの個数を表す.

   • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ai, Bi が空白を区切りとして書かれている.これは,
         i 番目のコンテナは時刻Ai にJOI 港に船で運ばれてきて,時刻Bi にトラックで運ばれていくことを
   表す.


出力

 標準出力に,コンテナを積み降ろしする方法は何通りあるかを1 000 000 007 で割った余りを1 行で出力
せよ.





                      港湾設備– 1 / 3

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

                                                                      Contest Day 1 – Port Facility


制限

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

   • 1 ≦N ≦1 000 000.

   • 1 ≦Ai ≦2N (1 ≦i ≦N).

   • 1 ≦Bi ≦2N (1 ≦i ≦N).

   • Ai < Bi (1 ≦i ≦N).

   • 2N 個の整数A1, · · · , AN, B1, · · · , BN は互いに異なる.


小課題

 この課題では小課題は全部で4 個ある.各小課題の配点および追加の制限は以下の通りである.

小課題1 [10 点]

   • N ≦20.


小課題2 [12 点]

   • N ≦2 000.


小課題3 [56 点]

   • N ≦100 000.


小課題4 [22 点]

 追加の制限はない.





                      港湾設備– 2 / 3

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

                                                                      Contest Day 1 – Port Facility


入出力例

  入力例1        出力例1
   4                    4
   1 3
   2 5
   4 8
   6 7

 この入力例では,4 通りの積み降ろしの方法が存在する.2 つの区画をA,B とする.条件を満たす積み
方は以下の通りである.

   • 1,2,3,4 番目のコンテナを,順に,A,B,A,A の区画に積む.

   • 1,2,3,4 番目のコンテナを,順に,A,B,A,B の区画に積む.

   • 1,2,3,4 番目のコンテナを,順に,B,A,B,A の区画に積む.

   • 1,2,3,4 番目のコンテナを,順に,B,A,B,B の区画に積む.


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

  入力例3        出力例3
   5                    8
   1 4
   2 10
   6 9
   7 8
   3 5

  入力例4        出力例4
   8                    16
   1 15
   2 5
   3 8
   4 6
   14 16
   7 9
   10 13
   11 12



                      港湾設備– 3 / 3