CODE FESTIVAL 2017 Elimination Tournament Round 1 (Parallel)

C - Paired Parentheses

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

長さ 2N の数列 a,b が与えられます。i 番目の要素はそれぞれ a_i,b_i です。すぬけくんはこの 2 つの数列を使って長さ 2N の バランスの取れた括弧列 のペア (s,t) の 美しさ を計算する仕事をしています。美しさは以下のように計算されます。

X=0 とする
1 以上 2N 以下の全ての i について、s_i = t_i ならば a_i を、そうでなければ b_i を X に加算する
最終的な X の値が (s,t) の美しさである

Q 個のクエリが与えられるので順番に処理してください。 i 番目のクエリでは a_{p_i} を x_i に、b_{p_i} を y_i に更新した後、バランスの取れた括弧列のペアの美しさとしてありうる値の最大値を求めてください。

この問題において、以下に示されるいずれかのみがバランスの取れた括弧列として定義されます。

空文字列
バランスの取れた括弧列 s について (,s, ) をこの順番で連結した文字列
バランスの取れた括弧列 s,t について s,t をこの順番で連結した文字列

制約

1 \leq N,Q \leq 10^{5}
-10^{9} \leq a_i,b_i,x_i,y_i \leq 10^{9}
1 \leq p_i \leq 2N
与えられる入力は全て整数

部分点

200 点分のデータセットでは N \leq 5,Q \leq 10 が成立する
300 点分のデータセットでは Q=1 が成立する

入力

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

N Q
a_1 a_2 ... a_{2N}
b_1 b_2 ... b_{2N}
p_1 x_1 y_1
:
p_Q x_Q y_Q

出力

答えを Q 行に出力せよ。i 行目には i 番目のクエリに対する応答を出力せよ。

入力例 1

出力例 1

15
15

1 番目のクエリにより、a=(1,4,7,3),b=(4,6,3,3) となります。(s,t) =(()(),()()) のとき、美しさが 15 となり、これが最大です。
2 番目のクエリにより、a=(1,4,2,3),b=(4,6,5,3) となります。(s,t) =(()(),(())) のとき、美しさが 15 となり、これが最大です。

入力例 2

7 7
34 -20 -27 42 44 29 9 11 20 44 27 19 -31 -29
46 -50 -11 20 28 46 12 13 33 -22 -48 -27 35 -17
7 27 34
12 -2 22
4 -50 -12
3 -32 15
8 -7 23
3 -30 11
4 -2 23

出力例 2

Score : 700 points

Problem Statement

You are given two sequences a and b, both of length 2N. The i-th elements in a and b are a_i and b_i, respectively. Using these sequences, Snuke is doing the job of calculating the beauty of pairs of balanced sequences of parentheses (defined below) of length 2N. The beauty of a pair (s,t) is calculated as follows:

Let X=0.
For each i between 1 and 2N (inclusive), increment X by a_i if s_i = t_i, and increment X by b_i otherwise.
The beauty of (s,t) is the final value of X.

You will be given Q queries. Process them in order. In the i-th query, update the value of a_{p_i} to x_i, and the value of b_{p_i} to y_i. Then, find the maximum possible beauty of a pair of balanced sequences of parentheses.

In this problem, only the sequences below are defined to be balanced sequences of parentheses.

An empty string
The concatenation of (, s, ) in this order, where s is a balanced sequence of parentheses
The concatenation of s, t in this order, where s and t are balanced sequences of parentheses

Constraints

1 \leq N,Q \leq 10^{5}
-10^{9} \leq a_i,b_i,x_i,y_i \leq 10^{9}
1 \leq p_i \leq 2N
All input values are integers.

Partial Scores

In the test set worth 200 points, N \leq 5 and Q \leq 10.
In the test set worth 300 points, Q = 1.

Input

Input is given from Standard Input in the following format:

N Q
a_1 a_2 ... a_{2N}
b_1 b_2 ... b_{2N}
p_1 x_1 y_1
:
p_Q x_Q y_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

Sample Output 1

15
15

The first query updates a and b to a=(1,4,7,3),b=(4,6,3,3). The maximum possible beauty is 15 for (s,t) =(()(),()()).
The second query updates a and b to a=(1,4,2,3),b=(4,6,5,3). The maximum possible beauty is 15 for (s,t) =(()(),(())).

Sample Input 2

7 7
34 -20 -27 42 44 29 9 11 20 44 27 19 -31 -29
46 -50 -11 20 28 46 12 13 33 -22 -48 -27 35 -17
7 27 34
12 -2 22
4 -50 -12
3 -32 15
8 -7 23
3 -30 11
4 -2 23

Sample Output 2

D - Ancient Tree Record

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

すぬけくんは N 頂点の木の記録を古代遺跡で見つけました。すぬけくんはこの記録から分かったことを以下にまとめました。

この木の頂点には 1,2,...,N の番号が、辺には 1,2,...,N-1 の番号がついていた
辺 i は頂点 a_i と b_i を双方向につないでいた
それぞれの辺の長さは 1 以上 10^{18} 以下の整数であった
頂点 i から頂点 1,...,N への最短距離の和が s_i であった

これらの情報から、それぞれの辺の長さを復元してください。 なお、与えられる記録において、これらの情報と矛盾しないように辺の長さを定めることが可能なことが保証されます。 さらに、そのような場合においてそれぞれの辺の長さが一意に定まることが証明できます。

制約

2 \leq N \leq 10^{5}
1 \leq a_i,b_i \leq N
1 \leq s_i \leq 10^{18}
与えられるグラフは木
与えられる入力は全て整数
与えられる情報から辺の長さは復元可能である
それぞれの辺の長さは 1 以上 10^{18} 以下の整数となる

部分点

300 点分のデータセットでは a_i = i,b_i = i+1 が成立する
別の 200 点分のデータセットでは N \geq 3, a_i = 1,b_i = i+1 が成立する

入力

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

N
a_1 b_1
:
a_{N-1} b_{N-1}
s_1 s_2 ... s_{N}

出力

答えを N-1 行に出力せよ。i 行目には辺 i の長さを出力せよ。

入力例 1

出力例 1

1
2
1

与えられるのは以下の図のような木の記録です

入力例 2

5
1 2
1 3
1 4
1 5
10 13 16 19 22

出力例 2

与えられるのは以下の図のような木の記録です

入力例 3

15
9 10
9 15
15 4
4 13
13 2
13 11
2 14
13 6
11 1
1 12
12 3
12 7
2 5
14 8
1154 890 2240 883 2047 2076 1590 1104 1726 1791 1091 1226 841 1000 901

出力例 3

Score : 800 points

Problem Statement

Snuke found a record of a tree with N vertices in ancient ruins. The findings are as follows:

The vertices of the tree were numbered 1,2,...,N, and the edges were numbered 1,2,...,N-1.
Edge i connected Vertex a_i and b_i.
The length of each edge was an integer between 1 and 10^{18} (inclusive).
The sum of the shortest distances from Vertex i to Vertex 1,...,N was s_i.

From the information above, restore the length of each edge. The input guarantees that it is possible to determine the lengths of the edges consistently with the record. Furthermore, it can be proved that the length of each edge is uniquely determined in such a case.