B. Buses

Codeforces

IDCF101B

Time2000ms

Memory265MB

Difficulty—

binary searchdata structuresdp

English · Original

Chinese · Translation

Formal · Original

Little boy Gerald studies at school which is quite far from his house. That's why he has to go there by bus every day. The way from home to school is represented by a segment of a straight line; the segment contains exactly _n_ + 1 bus stops. All of them are numbered with integers from 0 to _n_ in the order in which they follow from Gerald's home. The bus stop by Gerald's home has number 0 and the bus stop by the school has number _n_. There are _m_ buses running between the house and the school: the _i_\-th bus goes from stop _s__i_ to _t__i_ (_s__i_ < _t__i_), visiting all the intermediate stops in the order in which they follow on the segment. Besides, Gerald's no idiot and he wouldn't get off the bus until it is still possible to ride on it closer to the school (obviously, getting off would be completely pointless). In other words, Gerald can get on the _i_\-th bus on any stop numbered from _s__i_ to _t__i_ - 1 inclusive, but he can get off the _i_\-th bus only on the bus stop _t__i_. Gerald can't walk between the bus stops and he also can't move in the direction from the school to the house. Gerald wants to know how many ways he has to get from home to school. Tell him this number. Two ways are considered different if Gerald crosses some segment between the stops on different buses. As the number of ways can be too much, find the remainder of a division of this number by 1000000007 (109 + 7). ## Input The first line contains two space-separated integers: _n_ and _m_ (1 ≤ _n_ ≤ 109, 0 ≤ _m_ ≤ 105). Then follow _m_ lines each containing two integers _s__i_, _t__i_. They are the numbers of starting stops and end stops of the buses (0 ≤ _s__i_ < _t__i_ ≤ _n_). ## Output Print the only number — the number of ways to get to the school modulo 1000000007 (109 + 7). [samples] ## Note The first test has the only variant to get to school: first on bus number one to the bus stop number one; then on bus number two to the bus stop number two. In the second test no bus goes to the third bus stop, where the school is positioned. Thus, the correct answer is 0. In the third test Gerald can either get or not on any of the first four buses to get closer to the school. Thus, the correct answer is 24 = 16.

小男孩Gerald就读的学校离他家很远，因此他每天必须乘公交车上学。从家到学校的路线是一条直线段，该线段上恰好有 #cf_span[n + 1] 个公交站，编号为从 #cf_span[0] 到 #cf_span[n]，按离Gerald家由近及远的顺序排列。Gerald家附近的公交站编号为 #cf_span[0]，学校附近的公交站编号为 #cf_span[n]。在家中和学校之间有 #cf_span[m] 辆公交车运行：第 #cf_span[i] 辆公交车从站 #cf_span[si] 行驶到站 #cf_span[ti]（#cf_span[si < ti]），沿途按顺序停靠所有中间站点。此外，Gerald不是傻瓜，他不会在还能继续乘坐公交车更接近学校时就下车（显然，提前下车毫无意义）。换句话说，Gerald可以在编号从 #cf_span[si] 到 #cf_span[ti - 1]（含）的任意站点登上第 #cf_span[i] 辆公交车，但只能在站 #cf_span[ti] 下车。 Gerald不能在公交站之间步行，也不能朝从学校到家的方向移动。 Gerald想知道他有多少种方式从家到达学校。请告诉他这个数字。两种方式被认为是不同的，当且仅当他在某些站区间乘坐了不同的公交车。由于答案可能很大，请输出该数字对 #cf_span[1000000007]（即 #cf_span[109 + 7]）取模的结果。第一行包含两个用空格分隔的整数：#cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 109, 0 ≤ m ≤ 105]）。接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[si, ti]，分别表示每辆公交车的起点站和终点站编号（#cf_span[0 ≤ si < ti ≤ n]）。输出仅一个数字——从家到学校的方案数对 #cf_span[1000000007]（#cf_span[109 + 7]）取模的结果。第一个测试用例中，到达学校的唯一方式是：先乘坐第一辆公交车到第1号站，再乘坐第二辆公交车到第2号站。在第二个测试用例中，没有公交车到达学校所在的第3号站，因此正确答案是 #cf_span[0]。在第三个测试用例中，Gerald可以选择是否乘坐前四辆公交车中的任意一辆以更接近学校。因此正确答案是 #cf_span[24 = 16]。 ## Input 第一行包含两个用空格分隔的整数：#cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 109, 0 ≤ m ≤ 105]）。接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[si, ti]，分别表示每辆公交车的起点站和终点站编号（#cf_span[0 ≤ si < ti ≤ n]）。 ## Output 输出仅一个数字——从家到学校的方案数对 #cf_span[1000000007]（#cf_span[109 + 7]）取模的结果。 [samples] ## Note 第一个测试用例中，到达学校的唯一方式是：先乘坐第一辆公交车到第1号站，再乘坐第二辆公交车到第2号站。在第二个测试用例中，没有公交车到达学校所在的第3号站，因此正确答案是 #cf_span[0]。在第三个测试用例中，Gerald可以选择是否乘坐前四辆公交车中的任意一辆以更接近学校。因此正确答案是 #cf_span[24 = 16]。

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ m \in \mathbb{Z}_{\geq 0} $. Let $ B = \{(s_i, t_i) \mid i \in \{1, \dots, m\}\} $ be a set of bus routes, where $ 0 \leq s_i < t_i \leq n $. Let $ f(x) $ denote the number of ways to reach bus stop $ x $ from stop $ 0 $, with $ f(0) = 1 $. **Constraints** 1. $ 1 \leq n \leq 10^9 $ 2. $ 0 \leq m \leq 10^5 $ 3. For each bus $ (s_i, t_i) $: $ 0 \leq s_i < t_i \leq n $ **Objective** Compute $ f(n) \mod 1000000007 $, where for each bus $ (s_i, t_i) \in B $: $$ f(t_i) \gets f(t_i) + \sum_{x = s_i}^{t_i - 1} f(x) $$ and $ f(x) = 0 $ for all $ x > 0 $ initially except $ f(0) = 1 $. Due to the large $ n $, only the endpoints of buses and $ 0 $, $ n $ are relevant; use coordinate compression and dynamic programming over discrete points.

Samples

Input #1

2 2
0 1
1 2

Output #1

Input #2

3 2
0 1
1 2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Buses",
    "description": {
      "content": "Little boy Gerald studies at school which is quite far from his house. That's why he has to go there by bus every day. The way from home to school is represented by a segment of a straight line; the s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 271360
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF101B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Little boy Gerald studies at school which is quite far from his house. That's why he has to go there by bus every day. The way from home to school is represented by a segment of a straight line; the s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "小男孩Gerald就读的学校离他家很远，因此他每天必须乘公交车上学。从家到学校的路线是一条直线段，该线段上恰好有 #cf_span[n + 1] 个公交站，编号为从 #cf_span[0] 到 #cf_span[n]，按离Gerald家由近及远的顺序排列。Gerald家附近的公交站编号为 #cf_span[0]，学校附近的公交站编号为 #cf_span[n]。\n\n在家中和学校之间有 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ m \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ B = \\{(s_i, t_i) \\mid i \\in \\{1, \\dots, m\\}\\} $ be a set of bus routes, where $ 0 \\leq s_i < t_i \\leq n $.  \n\nLet $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments