← 返回题目列表

AtCoder · agc077_f

F. 两种类型的任务

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

分数: 1800 点

问题陈述

有 N 职位编号 1 通过 N,并且您想要完成它们 N 天。您每天只执行一项工作。

工作 i 可以在当天起的任何一天进行 L_i 全天 R_i。 这里,保证以下条件成立 L_i 和 R_i:

  • 1 \leq L_i \leq i \leq R_i \leq N
  • 1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N
  • 1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N

特别是,从第一个条件来看,可以完成所有 N 工作已结束 N 天。

此外,每个作业都有一种类型 L or R。最初,所有作业都是类型 R.

执行作业的成本定义如下:

  • 假设工作 i 于当天执行 x_i。如果工作 i 属于类型 L,成本定义为 x_i-L_i;如果它是类型 R,成本定义为 R_i-x_i.

从现在开始,将会有 N 将作业类型更改为 L。在 i-第查询,作业类型 P_i 更改为 L.

对于每个 k=0,1,\ldots,N,解决以下问题:

  • 考虑处理第一个之后的状态 k 查询。 找出所有可能的最小总成本 N 工作。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq L_i \leq i \leq R_i \leq N
  • 1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N
  • 1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N
  • (P_1,P_2,\ldots,P_N) 是一个排列 (1,2,\ldots,N).
  • 所有输入值均为整数。

输入

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
P_1 P_2 \ldots P_N

输出

对于每个 k=0,1,2,\ldots,N,按此顺序输出答案,用空格分隔。


示例输入 1

3
1 3
1 3
2 3
2 1 3

示例输出 1

3 1 1 2

每个人的最佳时间表 k 如下:

  • k=0:执行作业 1,2,3 的日子 分别为 1,2,3 。总成本是 (3-1)+(3-2)+(3-3)=3.
  • k=1:执行作业 1,2,3 的日子 分别为 2,1,3 。总成本是 (3-2)+(1-1)+(3-3)=1.
  • k=2:执行作业 1,2,3 的日子 分别为 1,2,3 。总成本是 (1-1)+(2-1)+(3-3)=1.
  • k=3:执行作业 1,2,3 的日子 分别为 1,2,3 。总成本是 (1-1)+(2-1)+(3-2)=2.

示例输入 2

4
1 4
2 4
3 4
4 4
1 2 3 4

示例输出 2

6 3 1 0 0

示例输入 3

8
1 5
1 5
2 6
2 6
3 7
3 8
5 8
5 8
5 8 7 3 2 6 4 1

示例输出 3

17 13 10 11 7 3 6 10 14

示例输入 4

15
1 4
1 4
1 8
2 8
2 11
2 11
3 11
3 11
4 12
5 12
5 13
8 14
11 15
11 15
12 15
15 13 9 3 8 11 6 5 12 2 4 7 14 1 10

示例输出 4

44 41 37 29 22 16 12 11 16 20 21 27 35 39 42 49