题目描述

小 $\gamma$ 发现有 $n$ 个城市按编号顺序分布在一条直线上，他想观察它们之间的势力影响情况。具体地，城市 $i$ 的影响力为 $p_i$，另有非负属性 $q_i, w_i$。为了减少特殊情况的讨论，我们保证所有城市的 $p$ 两两不同且不低于 $0$。

称 $u$ 能直接影响到 $v$ 当且仅当以下条件均成立（注意直接影响不满足传递性）：

• $v$ 在 $u$ 的势力范围内：$v \in [l_u, r_u]$。出于神秘原因，不保证 $u \in [l_u, r_u]$。
• 直线上 $u$ 与 $v$ 之间（不含 $u$ 且含 $v$）不存在城市 $x$ 满足 $p_x \geqslant p_u$。特别地，要求 $v \neq u$。

若 $u$ 能直接影响 $v$，则城市 $v$ 会定期向 $u$ 上贡：使者会携带 $w_v$ 的金钱从 $v$ 出发前往 $u$，每经过一个影响力 $p$ 大于此前所有城市（含 $v$）的城市 $x$，需要缴纳 $q_x$ 的过路费，若金钱不足即 $w_v$ 减去需缴纳的过路费后小于 $0$ 则上贡失败，否则可以对 $u$ 产生 $(d_{u, v} - a_v)^2 + b_v$ 的贡献值，其中 $d_{u, v} = p_u - p_v$。

令 $f_u$ 为在所有城市 $v$ 中 $v$ 对 $u$ 贡献值的最大值，若不存在城市对 $u$ 有贡献值则令 $f_u = 0$。小 $\gamma$ 希望你能对于所有 $u \in [1, n] \cap \mathbb N$，求出 $f_u$。

出于另外的神秘原因，对于一个城市 $u$，初始可得知 $p_u, l_u, r_u$，但 $q_u, w_u, a_u, b_u$ 与 $f_u$ 有关，在求出 $f_u$ 后才能得知。容易说明所有 $f_u$ 仍可唯一确定。

实现细节

本题暂仅支持 C++。

由于输入量较大，为减少输入所需时间并减轻评测机压力，我们使用交互的形式进行输入输出，你无需关注交互库细节，评测用交互库运行所需时间空间预计与下发的样例交互库相近。

你需要包含头文件 city.h。

你可以调用下述函数：

int get_subtask_id();
int get_p(const int u);
int get_q(const int u);
int get_w(const int u);
int get_l(const int u);
int get_r(const int u);
int get_a(const int u);
long long get_b(const int u);

依次会返回整数 $\mathtt{id}, p_u, q_u, w_u, l_u, r_u, a_u, b_u$。你需要保证变量 $\mathtt{u}$ 传入的参数在 $[1, n] \cap \mathbb N$ 中。交互库保证不会在函数调用过程中修改任何你定义的对象。$\mathtt{id}$ 若不为 $0$ 则表示该测试数据满足正式测试数据的第 $\mathtt{id}$ 个子任务的限制，保证所有正式测试数据中 $\mathtt{id}$ 均不为 $0$。

可以注意到你可以多次以相同的参数调用上述函数。

你还可以调用下述函数：

void print_f(const int u,const long long v);

表示你已经求出了 $f_u = v$。你需要保证变量 $\mathtt{u}$ 传入的参数在 $[1, n] \cap \mathbb N$ 中且对 $[1, n] \cap \mathbb N$ 中的每个数作为 $u$ 调用且仅调用一次。交互库保证不会在函数调用过程中修改任何你定义的对象。

注意 get_q，get_a，get_b 只有在你调用过相同 $u$ 的 print_f 后才会给出正确的值。

你需要实现下述函数解决题目描述中提到的问题：

void solve(const int n);

你可以在 solve 函数中调用上面提到的函数以获取给定的数据，需要调用 print_f 输出答案。

此外，你无需也不能实现主函数，不能定义以 grader 开头的命名空间。

样例转换器、样例交互库使用说明

你可以使用下发的 trans.cpp 编译得到的 trans 进行 ./trans text.in text.ans binary.in binary.ans，会将下述文本格式的 text.in text.ans 转化为样例二进制交互库 grader.cpp 所需的二进制格式的输入输出数据 binary.in binary.ans。

对于下述文本格式的输入输出数据，你也可直接使用下发的 grader_text.cpp。

对于 grader.cpp 二进制格式转化为下述文本格式的需求，你可以定义 long long 类型的数组 f，然后执行 FILE*fans=fopen("binary.ans","rb");fread(f+1,sizeof(long long),n,fans); 即可得到答案。对于输入数据，直接使用 grader.cpp 联合编译后进行调试输出即可。

输入格式

你无需关心评测用交互库的输入格式，下述为上面提到的文本格式输入的输入格式。

第 $1$ 行输入 $2$ 个整数 $\mathtt{id\ n}$。

第 $2$ 行至第 $n + 1$ 行中，第 $i + 1$ 行输入 $7$ 个整数 $\mathtt{p_i\ q_i\ w_i\ l_i\ r_i\ a_i\ b_i}$。

输出格式

你无需关心评测用交互库的输出格式，下述为上面提到的文本格式输出的输出格式。

$1$ 行输出 $n$ 个整数 $\mathtt{f_1\ f_2\ \dots\ f_n}$。

样例一

input

0 10
35697 8 1 1 10 -6 6
34242 4 4 10 10 -5 46
63943 1 16 1 10 -10 10
18471 4 13 9 10 -8 30
90918 10 1 1 10 4 48
89024 10 9 10 10 -10 4
93393 5 17 1 10 -5 28
50130 6 12 1 10 -8 6
69030 2 1 1 10 5 41
76068 8 4 5 8 -7 7

output

2131646 0 2068430430 0 5249727055 0 5614504930 0 357512470 673194922

样例二

input

0 20
7 12 7 10 20 7 82
6 15 15 1 17 2 97
4 8 15 1 19 -8 68
16 10 1 2 19 -7 1
17 6 1 6 20 -2 31
3 19 19 2 20 -7 48
2 6 11 1 20 -7 65
13 6 14 1 20 1 94
9 5 8 5 20 -3 52
11 13 13 15 20 -1 67
14 8 17 1 20 9 51
12 4 1 5 20 -4 59
1 11 18 3 19 -9 42
10 9 13 2 19 4 16
20 13 19 4 16 -5 66
8 17 9 1 18 0 24
19 13 19 20 20 -6 41
18 4 4 1 20 -7 19
5 1 20 2 19 1 19
15 11 18 10 18 3 30

output

0 168 0 468 667 129 0 389 0 0 526 442 0 366 826 0 31 163 0 0

样例三

input

1 10
51521 10 17 3 10 2 3
24070 6 9 3 10 8 38
8813 1 2 1 10 -4 12
45561 5 1 5 10 -3 40
63596 2 1 1 9 -1 17
22683 5 3 3 6 -7 9
67458 6 10 2 9 -8 38
39872 3 1 2 10 4 21
84195 4 20 1 9 -10 15
79586 4 3 1 10 -8 37

output

35557409 232898133 0 0 1674446409 0 2005427533 0 1964173782 0

限制与约定

$1 \leqslant n \leqslant 5 \times 10^5$ 且 $\forall i \in [1, n] \cap \mathbb N, 0 \leqslant p_i \leqslant 2 \times 10^6, 0 \leqslant q_i, w_i \leqslant 10^9, 1 \leqslant l_i \leqslant r_i \leqslant n, |a_i| \leqslant 2 \times 10^6, 0 \leqslant b_i \leqslant 4 \times 10^{12}$。

性质 $\texttt{A}$：$\forall i \in [1, n) \cap \mathbb N, p_i < p_{i + 1}$。

性质 $\texttt{B}$：$p_i$ 在范围内均匀随机生成。

性质 $\texttt{C}$：$l_i = 1$。

性质 $\texttt{D}$：$l_i = 1, r_i = n$。

性质 $\texttt{E}$：$q_i = 0$。

性质 $\texttt{F}$：$b_i = 0$。

性质 $\texttt{G}$：$a_i = b_i = 0$。

时间限制： $2.5\texttt{s}$（可以根据评测机速度修改）

空间限制： $1024\texttt{MB}$

下载

link