← 返回题目列表

AtCoder · abc342_e

H. 末班车

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

分数: 450 点

问题陈述

在AtCoder的国家,有 N 车站:车站 1,站 2, \ldots,站 N.

你被给予 M 有关该国火车的信息。的 i第-条信息 (1\leq i\leq M) 由六个正整数的元组表示 (l _ i,d _ i,k _ i,c _ i,A _ i,B _ i),对应以下信息:

  • 对于每个 t=l _ i,l _ i+d _ i,l _ i+2d _ i,\ldots,l _ i+(k _ i-1)d _ i,有一趟列车如下:
    • 列车出发站 A _ i 时间 t 并到达车站 B _ i 时间 t+c _ i.

除本信息描述的火车外,不存在其他火车,并且除了乘坐火车之外,不可能通过任何方式从一个车站移动到另一个车站。
另外,假设传输所需的时间可以忽略不计。

让 f(S) 是最晚可以到达车站的时间 N 从车站 S.
更准确地说, f(S) 定义为最大值 t 存在四个整数的元组序列 \big((t _ i,c _ i,A _ i,B _ i)\big) _ {i=1,2,\ldots,k} 满足以下所有条件:

  • t\leq t _ 1
  • A _ 1=S,B _ k=N
  • B _ i=A _ {i+1} 对于所有人 1\leq i\lt k,
  • 对于所有人 1\leq i\leq k,有车次从车站出发 A _ i 时间 t _ i 并到达车站 B _ i 时间 t _ i+c _ i.
  • t _ i+c _ i\leq t _ {i+1} 对于所有人 1\leq i\lt k.

如果没有这样的 t 存在,设置 f(S)=-\infty.

查找 f(1),f(2),\ldots,f(N-1).

约束

  • 2\leq N\leq2\times10 ^ 5
  • 1\leq M\leq2\times10 ^ 5
  • 1\leq l _ i,d _ i,k _ i,c _ i\leq10 ^ 9\ (1\leq i\leq M)
  • 1\leq A _ i,B _ i\leq N\ (1\leq i\leq M)
  • A _ i\neq B _ i\ (1\leq i\leq M)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
l _ 1 d _ 1 k _ 1 c _ 1 A _ 1 B _ 1
l _ 2 d _ 2 k _ 2 c _ 2 A _ 2 B _ 2
\vdots
l _ M d _ M k _ M c _ M A _ M B _ M

输出

打印 N-1 行。 的 k- 第行应包含 f(k) if f(k)\neq-\infty,和 Unreachable if f(k)=-\infty.


示例输入 1

6 7
10 5 10 3 1 3
13 5 10 2 3 4
15 5 10 7 4 6
3 10 2 4 2 5
7 10 2 3 5 6
5 3 18 2 2 3
6 3 20 4 2 1

示例输出 1

55
56
58
60
17

下图显示了该国运行的火车(省略了到达和出发时间的信息)。

考虑最晚可以到达车站的时间 6 从车站 2。 如下图所示,即可到达车站 6 从车站出发 2 时间 56 并作为车站移动 2\rightarrow 站 3\rightarrow 站 4\rightarrow 站 6.

无法出站 2 时间后 56 并到达车站 6,所以 f(2)=56.


示例输入 2

5 5
1000000000 1000000000 1000000000 1000000000 1 5
5 9 2 6 2 3
10 4 1 6 2 3
1 1 1 1 3 5
3 1 4 1 5 1

示例输出 2

1000000000000000000
Unreachable
1
Unreachable

有一趟车从车站出发 1 时间 10 ^ {18} 并到达车站 5 时间 10 ^ {18}+10 ^ 9。车站无列车出发 1 在那之后,所以 f(1)=10 ^ {18}。 正如这里所看到的,答案可能不适合 32\operatorname{bit} 整数。

另外,第二条和第三条信息都保证有火车从车站出发 2 时间 14 并到达车站 3 时间 20。 如图所示,某些列车可能会出现在多条信息中。


示例输入 3

16 20
4018 9698 2850 3026 8 11
2310 7571 7732 1862 13 14
2440 2121 20 1849 11 16
2560 5115 190 3655 5 16
1936 6664 39 8822 4 16
7597 8325 20 7576 12 5
5396 1088 540 7765 15 1
3226 88 6988 2504 13 5
1838 7490 63 4098 8 3
1456 5042 4 2815 14 7
3762 6803 5054 6994 10 9
9526 6001 61 8025 7 8
5176 6747 107 3403 1 5
2014 5533 2031 8127 8 11
8102 5878 58 9548 9 10
3788 174 3088 5950 3 13
7778 5389 100 9003 10 15
556 9425 9458 109 3 11
5725 7937 10 3282 2 9
6951 7211 8590 1994 15 12

示例输出 3

720358
77158
540926
255168
969295
Unreachable
369586
466218
343148
541289
42739
165772
618082
16582
591828