I:拉面
配点 : \(300\) 点
問題文
W大学街东西向直延,是一家竞争激烈的拉面店。 有许多摊位,有些开业后立即关闭,有些则长期营业。
拉面爱好者山田找到了关于这些店铺的记录。 该记录涵盖了从过去到现在W大学街上所有(N\)商店,每家拉面店\(i\)都提供了以下信息。
- 位于W街 \(d_i\)
- 开业日(第一个营业日)\(o_i\)
- 截止日(最后一个营业日)\(c_i\)
- 拉面店\(i\)还在营业,\(c_i = -1\)。
- 拉面美味指数 \(x_i\)
然而,所有商店都没有关于拉面价格p_i的信息。 对于收入有限的学生来说,售价极为重要。 山田感到困扰,咨询了熟悉拉面的加藤,得知W大学街的拉面价格有以下规定。
- 拉面店的售价 \(p_i i\) 是开业前一天,位于 W 大学街上的任何拉面店的最高 \(p_i\),且满足 \(p_i \leq \min( p_j + |d_i - d_j|^2 , x_i )\) 保持。
- 开业前一天,如果W大学街没有商店营业,\(p_i = x_i\)。
根据这些信息,请恢复\(N\)拉面店的价格。
制約
- \(1 \leq N \leq 10^5\)
- \(0 \leq d_i \leq 10^6\)
- \(1 \leq x_i \leq 10^{12}\)
- \(1 \leq o_i \leq c_i \leq 10^5\) 或 \(c_i = -1\)
- \(o_i \leq o_{i+1}\)
- 所有输入值都是整数。 如果您想走
入力
输入是按以下格式从标准输入给出的。
\(N\) \(o_1\) \(c_1\) \(d_1\) \(x_1\) \(\vdots\) \(o_N\) \(c_N\) \(d_N\) \(x_N\)
出力
\(N\) 行输出。 排在\(i\)中,输出拉面店的销售价格\(i\)。
入力例 1
4 1 6 1 5 2 11 3 10 3 6 4 2 8 11 4 15
出力例 1
5 9 2 10
入力例 2
7 1 5 106 662268024587 2 -1 131 151663457616 2 5 967 750705741256 2 6 95 614802747834 6 8 690 117869535832 7 7 644 14107192103 9 10 992 767668177628
出力例 2
662268024587 151663457616 662268765908 614802747834 117869535832 14107192103 117869627036
请注意,输入/输出值可以非常大。