← 返回题目列表

AtCoder · wupc2019_i

I. 拉面

中文机器翻译题面 查看原题
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

请注意,输入/输出值可以非常大。