E - Count Arithmetic Subarrays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

1\leq l\leq r\leq N を満たす整数の組 (l,r) であって、数列 (A_l,A_{l+1},\dots,A_r) が等差数列であるようなものが何通りあるか求めてください。

なお、数列 (x_1,x_2,\dots,x_{|x|}) が等差数列であるとは、ある d が存在して x_{i+1}-x_i=d\ (1\leq i < |x|) であることをいいます。 特に、長さ 1 の数列は常に等差数列です。

制約

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

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

4
3 6 9 3

出力例 1

8

条件を満たす整数の組 (l,r) は (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3) の 8 通りです。

実際、(l,r)=(1,3) のとき (A_l,\dots,A_r)=(3,6,9) は等差数列なので条件を満たしますが、 (l,r)=(2,4) のとき (A_l,\dots,A_r)=(6,9,3) は等差数列ではないので条件を満たしません。


入力例 2

5
1 1 1 1 1

出力例 2

15

すべての整数の組 (l,r)\ (1\leq l\leq r\leq 5) が条件を満たします。


入力例 3

8
87 42 64 86 72 58 44 30

出力例 3

22

Score : 300 points

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

  • 1\leq N \leq 2\times 10^5
  • 1\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 \dots A_N

Output

Print the answer.


Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.


Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.


Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22
F - Lining Up 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

人 1, 人 2,\ldots, 人 N の N 人が一列に並んでいます。

並び方の情報が長さ N の数列 A=(A _ 1,A _ 2,\ldots,A _ N) として与えられます。

A _ i\ (1\leq i\leq N) は次のような情報を表しています。

  • A _ i=-1 のとき、人 i は先頭に並んでいる。
  • A _ i\neq -1 のとき、人 i は人 A _ i のすぐ後ろに並んでいる。

列に並んでいる人の番号を先頭から順番に出力してください。

制約

  • 1\leq N\leq3\times10 ^ 5
  • A _ i=-1 もしくは 1\leq A _ i\leq N\ (1\leq i\leq N)
  • 情報と矛盾しないような N 人の並び方がただ 1 通り存在する
  • 入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

人 s _ 1, 人 s _ 2,\ldots, 人 s _ N がこの順に列に並んでいるとき、s _ 1,s _ 2,\ldots,s _ N をこの順に空白を区切りとして出力せよ。


入力例 1

6
4 1 -1 5 3 2

出力例 1

3 5 4 1 2 6

先頭から、人 3, 人 5, 人 4, 人 1, 人 2, 人 6 がこの順に列に並んでいるとき、与えられた情報と一致しています。

実際、

  • 人 1 は人 4 のすぐ後ろに並んでいます。
  • 人 2 は人 1 のすぐ後ろに並んでいます。
  • 人 3 は先頭に並んでいます。
  • 人 4 は人 5 のすぐ後ろに並んでいます。
  • 人 5 は人 3 のすぐ後ろに並んでいます。
  • 人 6 は人 2 のすぐ後ろに並んでいます。

となり、与えられた情報と一致していることが確認できます。

よって、3,5,4,1,2,6 をこの順に空白区切りで出力してください。


入力例 2

10
-1 1 2 3 4 5 6 7 8 9

出力例 2

1 2 3 4 5 6 7 8 9 10

入力例 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

出力例 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Score: 300 points

Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

  • if A _ i=-1, person i is at the front of the line;
  • if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

  • 1\leq N\leq3\times10 ^ 5
  • A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
  • There is exactly one way to arrange the N people consistent with the information given.
  • 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

If person s _ 1, person s _ 2, \ldots, person s _ N are standing in the line in this order, print s _ 1, s _ 2, \ldots, and s _ N in this order, separated by spaces.


Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

  • person 1 is standing right behind person 4,
  • person 2 is standing right behind person 1,
  • person 3 is at the front of the line,
  • person 4 is standing right behind person 5,
  • person 5 is standing right behind person 3, and
  • person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.


Sample Input 2

10
-1 1 2 3 4 5 6 7 8 9

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14
G - Snuke Panic (1D)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はすぬけ君たちを捕まえようとしています。

数直線上の座標 0,1,2,3,4 の 5 箇所に穴があり、すぬけ君たちの巣につながっています。

これから N 匹のすぬけ君が穴から出てきます。i 番目のすぬけ君は時刻 T_i に座標 X_i の穴から出てきて、大きさは A_i であることがわかっています。

高橋君は時刻 0 に座標 0 におり、数直線上を単位時間あたり 1 以下の速さで移動することができます。
すぬけ君が穴から出てきたのと同じ時刻に同じ座標に高橋君がいるとき、かつ、そのときに限り、高橋君はすぬけ君を捕まえることができます。
すぬけ君を捕まえるのにかかる時間は無視できます。

高橋君が適切に行動したとき、捕まえることができるすぬけ君の大きさの合計の最大値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
  • 0 \leq X_i \leq 4
  • 1 \leq A_i \leq 10^9
  • 入力に含まれる値は全て整数である

入力

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

N
T_1 X_1 A_1
T_2 X_2 A_2
\vdots
T_N X_N A_N

出力

答えを整数として出力せよ。


入力例 1

3
1 0 100
3 3 10
5 4 1

出力例 1

101

次のように行動するのが最適です。

  • 座標 0 で待機し、時刻 1 に 1 番目のすぬけ君を捕まえる
  • 座標 4 へ移動し、時刻 5 に 3 番目のすぬけ君を捕まえる

1 番目と 2 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。


入力例 2

3
1 4 1
2 4 1
3 4 1

出力例 2

0

高橋君はすぬけ君を 1 匹も捕まえることができません。


入力例 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

出力例 3

2978279323

Score : 400 points

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

  • 1 \leq N \leq 10^5
  • 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
  • 0 \leq X_i \leq 4
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
T_1 X_1 A_1
T_2 X_2 A_2
\vdots
T_N X_N A_N

Output

Print the answer as an integer.


Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

  • Wait at coordinate 0 to catch the first Snuke at time 1.
  • Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.


Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.


Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323
H - Lucky Numbers

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N-1 の整数列 S = (S_1, S_2, \ldots, S_{N-1}) および、「ラッキーナンバー」として M 個の相異なる整数 X_1, X_2, \ldots, X_M が与えられます。

長さ N の整数列 A = (A_1, A_2, \ldots, A_N) であって、次の条件を満たすものを「良い数列」と呼びます。

すべての i = 1, 2, \ldots, N-1 について、A_i + A_{i+1} = S_i が成り立つ。

良い数列 A を 1 つ選ぶときの、A の要素のうちラッキーナンバーであるものの個数(すなわち、A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace となる 1 以上 N 以下の整数 i の個数)としてあり得る最大値を求めてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10
  • -10^9 \leq S_i \leq 10^9
  • -10^9 \leq X_i \leq 10^9
  • X_1 \lt X_2 \lt \cdots \lt X_M
  • 入力はすべて整数

入力

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

N M
S_1 S_2 \ldots S_{N-1}
X_1 X_2 \ldots X_M

出力

良い数列 A を 1 つ選ぶときの、A の要素のうちラッキーナンバーであるものの個数としてありうる最大値を出力せよ。


入力例 1

9 2
2 3 3 4 -4 -7 -4 -1
-1 5

出力例 1

4

良い数列 A として A = (3, -1, 4, -1, 5, -9, 2, -6, 5) を選ぶと、A の要素のうちラッキーナンバーであるものは A_2, A_4, A_5, A_9 の 4 個となり、これが考えられる中で最大です。


入力例 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

出力例 2

8

Score : 500 points

Problem Statement

You are given a sequence of N-1 integers S = (S_1, S_2, \ldots, S_{N-1}), and M distinct integers X_1, X_2, \ldots, X_M, which are called lucky numbers.

A sequence of N integers A = (A_1, A_2, \ldots, A_N) satisfying the following condition is called a good sequence.

A_i + A_{i+1} = S_i holds for every i = 1, 2, \ldots, N-1.

Find the maximum possible number of terms that are lucky numbers in a good sequence A, that is, the maximum possible number of integers i between 1 and N such that A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10
  • -10^9 \leq S_i \leq 10^9
  • -10^9 \leq X_i \leq 10^9
  • X_1 \lt X_2 \lt \cdots \lt X_M
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
S_1 S_2 \ldots S_{N-1}
X_1 X_2 \ldots X_M

Output

Print the maximum possible number of terms that are lucky numbers in a good sequence A.


Sample Input 1

9 2
2 3 3 4 -4 -7 -4 -1
-1 5

Sample Output 1

4

A good sequence A = (3, -1, 4, -1, 5, -9, 2, -6, 5) contains four terms that are lucky numbers: A_2, A_4, A_5, A_9, which is the maximum possible count.


Sample Input 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

Sample Output 2

8
I - K-th Largest Triplet

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N),C=(C_1,C_2,\ldots,C_N) および整数 K が与えられます。

1\leq i,j,k\leq N を満たす整数 i,j,k の選び方 N^3 通りそれぞれに対して A_iB_j+B_jC_k+C_kA_i の値を計算したとき、その中で大きい方から K 番目の値を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq K\leq \min(N^3,5\times 10^5)
  • 1\leq A_i,B_i,C_i\leq 10^9
  • 入力は全て整数

入力

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

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_N

出力

答えを出力せよ。


入力例 1

2 5
1 2
3 4
5 6

出力例 1

31

N^3=8 個の整数の値は以下の通りです。

  • (i,j,k)=(1,1,1) : A_1B_1+B_1C_1+C_1A_1=1\times 3+3\times 5+5\times 1=23
  • (i,j,k)=(1,1,2) : A_1B_1+B_1C_2+C_2A_1=1\times 3+3\times 6+6\times 1=27
  • (i,j,k)=(1,2,1) : A_1B_2+B_2C_1+C_1A_1=1\times 4+4\times 5+5\times 1=29
  • (i,j,k)=(1,2,2) : A_1B_2+B_2C_2+C_2A_1=1\times 4+4\times 6+6\times 1=34
  • (i,j,k)=(2,1,1) : A_2B_1+B_1C_1+C_1A_2=2\times 3+3\times 5+5\times 2=31
  • (i,j,k)=(2,1,2) : A_2B_1+B_1C_2+C_2A_2=2\times 3+3\times 6+6\times 2=36
  • (i,j,k)=(2,2,1) : A_2B_2+B_2C_1+C_1A_2=2\times 4+4\times 5+5\times 2=38
  • (i,j,k)=(2,2,2) : A_2B_2+B_2C_2+C_2A_2=2\times 4+4\times 6+6\times 2=44

これらを値の降順に並べ替えると (44,38,36,34,31,29,27,23) となるため、 大きい方から 5 番目の値は 31 です。


入力例 2

3 10
100 100 100
100 100 100
100 100 100

出力例 2

30000

入力例 3

5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

出力例 3

689589940713840351

Score : 500 points

Problem Statement

You are given three integer sequences of length N, namely A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N), and C=(C_1,C_2,\ldots,C_N), and an integer K.

For each of the N^3 choices of integers i,j,k (1\leq i,j,k\leq N), compute the value A_iB_j + B_jC_k + C_kA_i. Among all these values, find the K-th largest value.

Constraints

  • 1\leq N \leq 2\times 10^5
  • 1\leq K \leq \min(N^3,5\times 10^5)
  • 1\leq A_i,B_i,C_i \leq 10^9
  • All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_N

Output

Print the answer.


Sample Input 1

2 5
1 2
3 4
5 6

Sample Output 1

31

The N^3=8 values are computed as follows:

  • For (i,j,k)=(1,1,1): A_1B_1+B_1C_1+C_1A_1=1\times 3+3\times 5+5\times 1=23
  • For (i,j,k)=(1,1,2): A_1B_1+B_1C_2+C_2A_1=1\times 3+3\times 6+6\times 1=27
  • For (i,j,k)=(1,2,1): A_1B_2+B_2C_1+C_1A_1=1\times 4+4\times 5+5\times 1=29
  • For (i,j,k)=(1,2,2): A_1B_2+B_2C_2+C_2A_1=1\times 4+4\times 6+6\times 1=34
  • For (i,j,k)=(2,1,1): A_2B_1+B_1C_1+C_1A_2=2\times 3+3\times 5+5\times 2=31
  • For (i,j,k)=(2,1,2): A_2B_1+B_1C_2+C_2A_2=2\times 3+3\times 6+6\times 2=36
  • For (i,j,k)=(2,2,1): A_2B_2+B_2C_1+C_1A_2=2\times 4+4\times 5+5\times 2=38
  • For (i,j,k)=(2,2,2): A_2B_2+B_2C_2+C_2A_2=2\times 4+4\times 6+6\times 2=44

Sorting these values in descending order, we have (44,38,36,34,31,29,27,23), so the 5th largest value is 31.


Sample Input 2

3 10
100 100 100
100 100 100
100 100 100

Sample Output 2

30000

Sample Input 3

5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

Sample Output 3

689589940713840351