A - The bottom of the ninth

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

問題文

チーム高橋とチーム青木が、チーム高橋を先攻として野球を行なっています。
現在、9 回表までが終了し、9 回裏が始まろうとしています。

試合において、チーム高橋は i 回表 (1\leq i\leq 9)A_i 点を取り、チーム青木は j 回裏 (1\leq j\leq 8)B_j 点を取りました。
ここで、9 回表の終了時点でチーム高橋の得点はチーム青木の得点以上です。
チーム青木は 9 回裏に最低何点取れば勝利することができるか求めてください。

ただし、9 回裏の終了時点で同点であった場合は引き分けとなり、すなわちチーム青木が勝利するためには 9 回裏の終了時点でチーム高橋より真に多くの点をとっている必要があるものとします。
なお、(ある時点における)チーム高橋の得点はそれまでの回の表に取った点数の合計であり、チーム青木の得点はそれまでの回の裏に取った点数の合計です。

制約

  • 0\leq A_i, B_j\leq 99
  • A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
  • 入力はすべて整数

入力

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

A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9
B_1 B_2 B_3 B_4 B_5 B_6 B_7 B_8

出力

チーム青木が勝利するために 9 回裏に取る必要のある最小の得点を出力せよ。


入力例 1

0 1 0 1 2 2 0 0 1
1 1 0 0 0 0 1 0

出力例 1

5

9 回表の終了時点でチーム高橋の得点は 7 点、チーム青木の得点は 3 点となっています。
よって、チーム青木は9 回裏に 5 点取れば 7-8 となり、勝利することができます。
9 回裏に 4 点では、引き分けとなり勝利できないことに注意してください。


入力例 2

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

出力例 2

1

Score: 100 points

Problem Statement

Team Takahashi and Team Aoki are playing a baseball game, with Team Takahashi batting first.
Currently, the game has finished through the top of the ninth inning, and the bottom of the ninth is about to begin.

Team Takahashi scored A_i runs in the top of the i-th inning (1\leq i\leq 9), and Team Aoki scored B_j runs in the bottom of the j-th inning (1\leq j\leq 8).
At the end of the top of the ninth, Team Takahashi's score is not less than Team Aoki's score.
Determine the minimum number of runs Team Aoki needs to score in the bottom of the ninth to win the game.

Here, if the game is tied at the end of the bottom of the ninth, it results in a draw. Therefore, for Team Aoki to win, they must score strictly more runs than Team Takahashi by the end of the bottom of the ninth.
Team Takahashi's score at any point is the total runs scored in the tops of the innings up to that point, and Team Aoki's score is the total runs scored in the bottoms of the innings.

Constraints

  • 0\leq A_i, B_j\leq 99
  • A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 + A_9 \geq B_1 + B_2 + B_3 + B_4 + B_5 + B_6 + B_7 + B_8
  • All input values are integers.

Input

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

A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9
B_1 B_2 B_3 B_4 B_5 B_6 B_7 B_8

Output

Print the minimum number of runs Team Aoki needs to score in the bottom of the ninth inning to win.


Sample Input 1

0 1 0 1 2 2 0 0 1
1 1 0 0 0 0 1 0

Sample Output 1

5

At the end of the top of the ninth inning, Team Takahashi has scored seven runs, and Team Aoki has scored three runs.
Therefore, if Team Aoki scores five runs in the bottom of the ninth, the scores will be 7-8, allowing them to win.
Note that scoring four runs would result in a draw and not a victory.


Sample Input 2

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Sample Output 2

1
B - Spot the Difference

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150

問題文

N マス、横 N マスのグリッドが 2 個与えられます。それぞれグリッド A, グリッド B と呼びます。
グリッドの各マスには英小文字が書かれています。
グリッド A の上から i 行目、左から j 列目に書かれている文字は A_{i, j} です。
グリッド B の上から i 行目、左から j 列目に書かれている文字は B_{i, j} です。

2 つのグリッドは 1 ヵ所だけ書かれている文字が異なります。すなわち、A_{i, j} \neq B_{i, j} である N 以下の正整数の組 (i, j) はちょうど 1 個存在します。この (i, j) を求めてください。

制約

  • 1 \leq N \leq 100
  • A_{i, j}, B_{i, j} は全て英小文字
  • A_{i, j} \neq B_{i, j} である (i, j) がちょうど 1 個存在する

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

出力

A_{i, j} \neq B_{i, j} である N 以下の正整数の組を (i, j) とする。この時、(i, j) を以下の形式で出力せよ。

i j

入力例 1

3
abc
def
ghi
abc
bef
ghi

出力例 1

2 1

A_{2, 1} = dB_{2, 1} = b なので A_{2, 1} \neq B_{2, 1} が成り立つため、(i, j) = (2, 1) は問題文の条件を満たします。


入力例 2

1
f
q

出力例 2

1 1

入力例 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

出力例 3

5 9

Score: 150 points

Problem Statement

You are given two grids, each with N rows and N columns, referred to as grid A and grid B.
Each cell in the grids contains a lowercase English letter.
The character at the i-th row and j-th column of grid A is A_{i, j}.
The character at the i-th row and j-th column of grid B is B_{i, j}.

The two grids differ in exactly one cell. That is, there exists exactly one pair (i, j) of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Find this (i, j).

Constraints

  • 1 \leq N \leq 100
  • A_{i, j} and B_{i, j} are all lowercase English letters.
  • There exists exactly one pair (i, j) such that A_{i, j} \neq B_{i, j}.

Input

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Output

Let (i, j) be the pair of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Print (i, j) in the following format:

i j

Sample Input 1

3
abc
def
ghi
abc
bef
ghi

Sample Output 1

2 1

From A_{2, 1} = d and B_{2, 1} = b, we have A_{2, 1} \neq B_{2, 1}, so (i, j) = (2, 1) satisfies the condition in the problem statement.


Sample Input 2

1
f
q

Sample Output 2

1 1

Sample Input 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

Sample Output 3

5 9
C - Merge the balls

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250

問題文

空の列と、N 個のボールがあります。i 個目 (1\leq i\leq N) のボールの大きさは 2^{A_i} です。

これから N 回の操作を行います。
i 回目の操作では、i 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。

  1. 列にあるボールが 1 つ以下ならば操作を終了する。
  2. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 異なる ならば操作を終了する。
  3. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 等しい ならば、2 つのボールを取り除き、「取り除かれた 2 つのボールの大きさの和」の大きさのボール 1 つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。

N 回の操作の後で、列にあるボールの数を求めてください。

制約

  • 1\leq N \leq 2\times 10^5
  • 0\leq A_i\leq 10^9
  • 入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

N 回の操作の後で、列にあるボールの数を出力せよ。


入力例 1

7
2 1 1 3 5 3 3

出力例 1

3

操作は次のように行われます。

  • 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^2 です。
  • 2 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^2, 2^1 です。
  • 3 回目の操作の後、列にあるボールは 1 つで、大きさは 2^3 です。これは次のようにして得ることができます。
    • 3 回目の操作において 3 個目のボールを付け加えたとき、列にあるボールの大きさは順に 2^2,2^1,2^1 となります。
    • 右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^1+2^1=2^2 のボールが追加されます。このとき、列にあるボールの大きさは 2^2, 2^2 となります。
    • さらに、再び右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^2+2^2=2^3 のボールが追加され、列にあるボールの大きさは 2^3 となります。
  • 4 回目の操作の後、列にあるボールは 1 つで、大きさは 2^4 です。
  • 5 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^4, 2^5 です。
  • 6 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^3 です。
  • 7 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^4 です。

よって、最後に列にあるボールの数である 3 を出力します。


入力例 2

5
0 0 0 1 2

出力例 2

4

操作は次のように行われます。

  • 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^0 です。
  • 2 回目の操作の後、列にあるボールは 1 つで、大きさは 2^1 です。
  • 3 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^1, 2^0 です。
  • 4 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^1, 2^0, 2^1 です。
  • 5 回目の操作の後、列にあるボールは 4 つで、大きさは順に 2^1, 2^0, 2^1, 2^2 です。

よって、最後に列にあるボールの数である 4 を出力します。

Score: 250 points

Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

  1. If the sequence has one or fewer balls, end the operation.
  2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
  3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the number of balls in the sequence after the N operations.


Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

  • After the first operation, the sequence has one ball, of size 2^2.
  • After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
  • After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
    • When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
    • The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
    • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
  • After the fourth operation, the sequence has one ball, of size 2^4.
  • After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
  • After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
  • After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.


Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

  • After the first operation, the sequence has one ball, of size 2^0.
  • After the second operation, the sequence has one ball, of size 2^1.
  • After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
  • After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
  • After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.

D - Grid and Magnet

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 425

問題文

HW 列のマス目があり、いくつか(0 個のこともある)のマスには磁石が置かれています。
マス目の状態は H 個の 長さ W の文字列 S_1,S_2,\ldots,S_H で表され、 S_ij 文字目が # のとき上から i 行目かつ左から j 列目のマスには磁石が置かれていることを、 . のとき何も置かれていないことを表しています。

高橋君は鉄の鎧を着ており、あるマスにいるとき次のように移動することができます。

  • 現在いるマスの上下左右に隣り合うマスのいずれかに磁石が置かれているとき、どこへも移動することができない。
  • そうでないとき、上下左右に隣り合うマスのいずれかを選んでそのマスに移動することができる。
    ただし、マス目の外に移動することはできない。

磁石が置かれていない各マスについて、そのマスの自由度を、「最初高橋くんがそのマスにいるとき、そこから移動を繰り返して到達できるマスの個数」として定義します。 マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を求めてください。

ただし、自由度の定義において、「移動を繰り返して到達できるマス」とは、最初にいるマスからそのマスまで移動を繰り返して到達する方法(1 回も移動しないものも含む)が 1 つ以上存在するようなマスのことであり、 最初のマスから始めてすべてのそのようなマスを巡るような移動方法が存在する必要はありません。特に(磁石の置かれていない)各マス自身は、そのマスから「移動を繰り返して到達できるマス」につねに含まれることに注意してください。

制約

  • 1\leq H,W\leq 1000
  • H,W は整数
  • S_i.# のみからなる長さ W の文字列
  • 磁石の置かれていないマスが少なくとも 1 つ存在する。

入力

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

H W
S_1
S_2
\vdots
S_H

出力

マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を出力せよ。


入力例 1

3 5
.#...
.....
.#..#

出力例 1

9

上から i 行目かつ左から j 列目のマスを (i,j) で表します。 高橋君が最初に (2,3) にいるとき、高橋君の移動の例としては次のようなものなどが考えられます。

  • (2,3)\to (2,4)\to (1,4)\to (1,5)\to (2,5)
  • (2,3)\to (2,4)\to (3,4)
  • (2,3)\to (2,2)
  • (2,3)\to (1,3)
  • (2,3)\to (3,3)

よって、途中で到達しているマスも含めて高橋君は (2,3) から少なくとも 9 個のマスに到達することができます。 一方、これら以外のマスには到達することができないため、(2,3) の自由度は 9 となります。

これは磁石が置かれていない各マスの自由度のうち最大であるため、9 を出力します。


入力例 2

3 3
..#
#..
..#

出力例 2

1

磁石が置かれていないどのマスについても、上下左右に隣り合うマスのいずれかに磁石が置かれています。
よって、磁石が置かれていないどのマスからも移動することはできず、マスの自由度は 1 となります。
そのため、1 を出力します。

Score: 425 points

Problem Statement

There is a grid of H rows and W columns. Some cells (possibly zero) contain magnets.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H of length W. If the j-th character of S_i is #, it indicates that there is a magnet in the cell at the i-th row from the top and j-th column from the left; if it is ., it indicates that the cell is empty.

Takahashi, wearing an iron armor, can move in the grid as follows:

  • If any of the cells vertically or horizontally adjacent to the current cell contains a magnet, he cannot move at all.
  • Otherwise, he can move to any one of the vertically or horizontally adjacent cells.
    However, he cannot exit the grid.

For each cell without a magnet, define its degree of freedom as the number of cells he can reach by repeatedly moving from that cell. Find the maximum degree of freedom among all cells without magnets in the grid.

Here, in the definition of degree of freedom, "cells he can reach by repeatedly moving" mean cells that can be reached from the initial cell by some sequence of moves (possibly zero moves). It is not necessary that there is a sequence of moves that visits all such reachable cells starting from the initial cell. Specifically, each cell itself (without a magnet) is always included in the cells reachable from that cell.

Constraints

  • 1 \leq H, W \leq 1000
  • H and W are integers.
  • S_i is a string of length W consisting of . and #.
  • There is at least one cell without a magnet.

Input

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

H W
S_1
S_2
\vdots
S_H

Output

Print the maximum degree of freedom among all cells without magnets.


Sample Input 1

3 5
.#...
.....
.#..#

Sample Output 1

9

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. If Takahashi starts at (2,3), possible movements include:

  • (2,3) \to (2,4) \to (1,4) \to (1,5) \to (2,5)
  • (2,3) \to (2,4) \to (3,4)
  • (2,3) \to (2,2)
  • (2,3) \to (1,3)
  • (2,3) \to (3,3)

Thus, including the cells he passes through, he can reach at least nine cells from (2,3).
Actually, no other cells can be reached, so the degree of freedom for (2,3) is 9.

This is the maximum degree of freedom among all cells without magnets, so print 9.


Sample Input 2

3 3
..#
#..
..#

Sample Output 2

1

For any cell without a magnet, there is a magnet in at least one of the adjacent cells.
Thus, he cannot move from any of these cells, so their degrees of freedom are 1.
Therefore, print 1.

E - Jump Distance Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

座標平面上に N 個の点 P_1,P_2,\ldots,P_N があり、点 P_i の座標は (X_i,Y_i) です。
2 つの点 A,B の距離 \text{dist}(A,B) を次のように定義します。

最初、ウサギが点 A にいる。
(x,y) にいるウサギは (x+1,y+1), (x+1,y-1), (x-1,y+1), (x-1,y-1) のいずれかに 1 回のジャンプで移動することができる。
A から点 B まで移動するために必要なジャンプの回数の最小値を \text{dist}(A,B) として定義する。
ただし、何度ジャンプを繰り返しても点 A から点 B まで移動できないとき、\text{dist}(A,B)=0 とする。

\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i,P_j) を求めてください。

制約

  • 2\leq N\leq 2\times 10^5
  • 0\leq X_i,Y_i\leq 10^8
  • i\neq j ならば (X_i,Y_i)\neq (X_j,Y_j)
  • 入力はすべて整数

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i,P_j) の値を整数で出力せよ。


入力例 1

3
0 0
1 3
5 6

出力例 1

3

P_1,P_2,P_3 の座標はそれぞれ (0,0), (1,3), (5,6) です。
P_1 から P_2 へはウサギは (0,0)\to (1,1)\to (0,2)\to (1,3)3 回で移動でき、2 回以下では P_1 から P_2 まで移動できないため、
\text{dist}(P_1,P_2)=3 です。
P_1 から P_3 および P_2 から P_3 へはウサギは移動できないため、\text{dist}(P_1,P_3)=\text{dist}(P_2,P_3)=0 となります。

よって、答えは \displaystyle\sum_{i=1}^{2}\displaystyle\sum_{j=i+1}^3\text{dist}(P_i,P_j)=\text{dist}(P_1,P_2)+\text{dist}(P_1,P_3)+\text{dist}(P_2,P_3)=3+0+0=3 となります。


入力例 2

5
0 5
1 7
2 9
3 8
4 6

出力例 2

11

Score: 500 points

Problem Statement

On a coordinate plane, there are N points P_1, P_2, \ldots, P_N, where point P_i has coordinates (X_i, Y_i).
The distance \text{dist}(A, B) between two points A and B is defined as follows:

A rabbit is initially at point A.
A rabbit at position (x, y) can jump to (x+1, y+1), (x+1, y-1), (x-1, y+1), or (x-1, y-1) in one jump.
\text{dist}(A, B) is defined as the minimum number of jumps required to get from point A to point B.
If it is impossible to get from point A to point B after any number of jumps, let \text{dist}(A, B) = 0.

Calculate the sum \displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j).

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq X_i, Y_i \leq 10^8
  • For i \neq j, (X_i, Y_i) \neq (X_j, Y_j)
  • All input values are integers.

Input

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the value of \displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j) as an integer.


Sample Input 1

3
0 0
1 3
5 6

Sample Output 1

3

P_1, P_2, and P_3 have coordinates (0,0), (1,3), and (5,6), respectively.
The rabbit can get from P_1 to P_2 in three jumps via (0,0) \to (1,1) \to (0,2) \to (1,3), but not in two or fewer jumps,
so \text{dist}(P_1, P_2) = 3.
The rabbit cannot get from P_1 to P_3 or from P_2 to P_3, so \text{dist}(P_1, P_3) = \text{dist}(P_2, P_3) = 0.

Therefore, the answer is \displaystyle\sum_{i=1}^{2}\displaystyle\sum_{j=i+1}^3\text{dist}(P_i, P_j)=\text{dist}(P_1, P_2)+\text{dist}(P_1, P_3)+\text{dist}(P_2, P_3)=3+0+0=3.


Sample Input 2

5
0 5
1 7
2 9
3 8
4 6

Sample Output 2

11
F - Double Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

整数列 A = (A_1, A_2, \dots, A_N) が与えられます。
次の式を計算してください。

\displaystyle \sum_{i=1}^N \sum_{j=i+1}^N \max(A_j - A_i, 0)


なお、制約下において答えが 2^{63} 未満となることは保証されています。

制約

  • 2 \leq N \leq 4 \times 10^5
  • 0 \leq A_i \leq 10^8
  • 入力される値は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

式の値を出力せよ。


入力例 1

3
2 5 3

出力例 1

4

(i, j) = (1, 2) のとき \max(A_j - A_i, 0) = \max(3, 0) = 3 です。
(i, j) = (1, 3) のとき \max(A_j - A_i, 0) = \max(1, 0) = 1 です。
(i, j) = (2, 3) のとき \max(A_j - A_i, 0) = \max(-2, 0) = 0 です。
これらを足し合わせた 3 + 1 + 0 = 4 が答えとなります。


入力例 2

10
5 9 3 0 4 8 7 5 4 0

出力例 2

58

Score: 500 points

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N).
Calculate the following expression:

\displaystyle \sum_{i=1}^N \sum_{j=i+1}^N \max(A_j - A_i, 0)


The constraints guarantee that the answer is less than 2^{63}.

Constraints

  • 2 \leq N \leq 4 \times 10^5
  • 0 \leq A_i \leq 10^8
  • All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Print the value of the expression.


Sample Input 1

3
2 5 3

Sample Output 1

4

For (i, j) = (1, 2), we have \max(A_j - A_i, 0) = \max(3, 0) = 3.
For (i, j) = (1, 3), we have \max(A_j - A_i, 0) = \max(1, 0) = 1.
For (i, j) = (2, 3), we have \max(A_j - A_i, 0) = \max(-2, 0) = 0.
Adding these together gives 3 + 1 + 0 = 4, which is the answer.


Sample Input 2

10
5 9 3 0 4 8 7 5 4 0

Sample Output 2

58
G - Hash on Tree

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 650

問題文

頂点に 1 から N の番号がついた N 頂点の根付き木があります。
頂点 1 が根で、頂点 i (2 \leq i \leq N) の親は頂点 p_i です。(p_i \lt i)
また、数列 A = (A_1, A_2, \dots, A_N) があります。

根付き木の ハッシュ値 を次の手順によって得られる値とします。

  • f(n) (1 \leq n \leq N)n = N, N-1, \dots, 2, 1 の順に次の計算をすることで得られる値とする。
    • 頂点 n が葉の場合、f(n) = A_n とする。
    • 頂点 n が葉でない場合、n の子からなる集合を C(n) として \displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c) とする。
  • f(1) \bmod{998244353} を根付き木のハッシュ値とする。

Q 個のクエリを与えられる順に処理してください。
各クエリでは v, x が与えられるので、A_v の値を x に更新した後、根付き木のハッシュ値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq p_i \lt i
  • 0 \leq A_i \lt 998244353
  • 1 \leq v \leq N
  • 0 \leq x \lt 998244353
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_ii 番目のクエリを意味する。

N Q 
p_2 p_3 \dots p_N
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは次の形式で与えられる。

v x

出力

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


入力例 1

3 2
1 1
3 5 1
3 4
2 1

出力例 1

23
7

はじめ、A = (3, 5, 1) です。
1 番目のクエリは次のように処理されます。

  • A_34 に更新する。A = (3, 5, 4) となる。
  • 根付き木のハッシュ値は以下の手順により 23 となるので、これを出力する。
    • 頂点 3 は子を持たない。よって f(3) = 4 である。
    • 頂点 2 は子を持たない。よって f(2) = 5 である。
    • 頂点 1 は頂点 2, 3 を子に持つ。よって f(1) = 3 + 5 \times 4 = 23 である。
    • f(1) \bmod{998244353} = 23 を根付き木のハッシュ値とする。

2 番目のクエリは次のように処理されます。

  • A_21 に更新する。A = (3, 1, 4) となる。
  • 根付き木のハッシュ値は以下の手順により 7 となるので、これを出力する。
    • 頂点 3 は子を持たない。よって f(3) = 4 である。
    • 頂点 2 は子を持たない。よって f(2) = 1 である。
    • 頂点 1 は頂点 2, 3 を子に持つ。よって f(1) = 3 + 1 \times 4 = 7 である。
    • f(1) \bmod{998244353} = 7 を根付き木のハッシュ値とする。

入力例 2

5 4
1 1 2 2
2 5 4 4 1
3 3
5 0
4 5
5 2

出力例 2

29
17
17
47

入力例 3

10 10
1 2 1 2 5 6 3 5 1
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044
1 21524934
9 529970099
6 757265587
8 219853537
5 687675301
5 844033519
8 780395611
2 285523485
6 13801766
3 487663184

出力例 3

876873846
952166813
626349486
341294449
466546009
331098453
469507939
414882732
86695436
199797684

Score: 650 points

Problem Statement

You are given a rooted tree with N vertices numbered 1 to N.
Vertex 1 is the root, and the parent of vertex i (2 \leq i \leq N) is vertex p_i (p_i < i).
Additionally, there is a sequence A = (A_1, A_2, \dots, A_N).

The hash value of the rooted tree is calculated as follows:

  • Define f(n) (1 \leq n \leq N) as follows in the order n = N, N-1, \dots, 2, 1.
    • If vertex n is a leaf, f(n) = A_n.
    • If vertex n is not a leaf, \displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c), where C(n) is the set of children of n.
  • The hash value of the rooted tree is f(1) \bmod{998244353}.

Process Q queries in the order they are given.
Each query provides v and x, so update A_v to x and then compute the hash value of the rooted tree.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq p_i < i
  • 0 \leq A_i < 998244353
  • 1 \leq v \leq N
  • 0 \leq x < 998244353
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i represents the i-th query:

N Q 
p_2 p_3 \dots p_N
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

v x

Output

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


Sample Input 1

3 2
1 1
3 5 1
3 4
2 1

Sample Output 1

23
7

Initially, A = (3, 5, 1).
The first query is processed as follows:

  • Update A_3 to 4. Now A = (3, 5, 4).
  • The hash value of the rooted tree is calculated as follows to be 23, which should be printed.
    • Vertex 3 has no children. Thus, f(3) = 4.
    • Vertex 2 has no children. Thus, f(2) = 5.
    • Vertex 1 has children 2 and 3. Thus, f(1) = 3 + 5 \times 4 = 23.
    • f(1) \bmod{998244353} = 23 is the hash value of the rooted tree.

The second query is processed as follows:

  • Update A_2 to 1. Now A = (3, 1, 4).
  • The hash value of the rooted tree is calculated as follows to be 7:
    • Vertex 3 has no children. Thus, f(3) = 4.
    • Vertex 2 has no children. Thus, f(2) = 1.
    • Vertex 1 has children 2 and 3. Thus, f(1) = 3 + 1 \times 4 = 7.
    • f(1) \bmod{998244353} = 7 is the hash value of the rooted tree.

Sample Input 2

5 4
1 1 2 2
2 5 4 4 1
3 3
5 0
4 5
5 2

Sample Output 2

29
17
17
47

Sample Input 3

10 10
1 2 1 2 5 6 3 5 1
766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044
1 21524934
9 529970099
6 757265587
8 219853537
5 687675301
5 844033519
8 780395611
2 285523485
6 13801766
3 487663184

Sample Output 3

876873846
952166813
626349486
341294449
466546009
331098453
469507939
414882732
86695436
199797684