AT_agc077_f.[AGC077F] Two Types of Tasks

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

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

仕事 $ i $ は， $ L_i $ 日目から $ R_i $ 日目までのいずれかの日に行うことができます．ここで， $ L_i,R_i $ に関して，以下の条件が満たされることが保証されます．

特に最初の条件より， $ 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 $ に対して，次の問題を解いて下さい．

入力は以下の形式で標準入力から与えられる．

$ 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 $ に対する答えをこの順に空白区切りで出力せよ．

输入#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

各 $ 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 $ になる．

输入解题思路，AI测评打分。不知道怎么写?