F - Two Types of Tasks 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 1800 点

問題文

1 から N までの番号がついた N 個の仕事があり，これらを N 日間で終わらせたいです． 1 日にちょうど 1 つの仕事を行います．

仕事 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 または R のタイプが定まっています． 最初，すべての仕事はタイプ R です．

仕事を行うコストを以下のように定義します．

  • 仕事 i を x_i 日目に行うとする．仕事 i がタイプ L ならコストを x_i-L_i と定め，タイプ R ならコストを R_i-x_i と定める．

今から，仕事のタイプを L に変更するクエリが N 回来ます． 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

Score : 1800 points

Problem Statement

There are N jobs numbered 1 through N, and you want to complete them over N days. You perform exactly one job per day.

Job i can be performed on any day from day L_i through day R_i. Here, the following conditions are guaranteed to hold for L_i and 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

Particularly, from the first condition, it follows that it is possible to complete all N jobs over N days.

Furthermore, each job has a type of L or R. Initially, all jobs are of type R.

The cost of performing a job is defined as follows:

  • Suppose job i is performed on day x_i. If job i is of type L, the cost is defined as x_i-L_i; if it is of type R, the cost is defined as R_i-x_i.

From now on, there will be N queries that change the type of a job to L. In the i-th query, the type of job P_i is changed to L.

For each k=0,1,\ldots,N, solve the following problem:

  • Consider the state after processing the first k queries. Find the minimum possible total cost of all N jobs.

Constraints

  • 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) is a permutation of (1,2,\ldots,N).
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

For each k=0,1,2,\ldots,N, output the answer in this order, separated by spaces.

Sample Input 1

3
1 3
1 3
2 3
2 1 3

Sample Output 1

3 1 1 2

An optimal schedule for each k is as follows:

  • k=0: Perform jobs 1,2,3 on days 1,2,3 respectively. The total cost is (3-1)+(3-2)+(3-3)=3.
  • k=1: Perform jobs 1,2,3 on days 2,1,3 respectively. The total cost is (3-2)+(1-1)+(3-3)=1.
  • k=2: Perform jobs 1,2,3 on days 1,2,3 respectively. The total cost is (1-1)+(2-1)+(3-3)=1.
  • k=3: Perform jobs 1,2,3 on days 1,2,3 respectively. The total cost is (1-1)+(2-1)+(3-2)=2.

Sample Input 2

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

Sample Output 2

6 3 1 0 0

Sample Input 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

Sample Output 3

17 13 10 11 7 3 6 10 14

Sample Input 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

Sample Output 4

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