E - Approximate Equalization 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

整数列 A=(A_1,A_2,\dots,A_N) があります。 あなたは次の操作を好きな回数(0 回でもよい)行うことができます。

  • 1\leq i,j \leq N を満たす整数 i,j を選ぶ。A_i を 1 減らし、A_j を 1 増やす。

A の最小値と最大値の差を 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
4 7 3 7

出力例 1

3

以下のように 3 回の操作を行うことで、A の最小値と最大値の差を 1 以下にすることができます。

  • i=2,j=3 として操作を行う。A=(4,6,4,7) になる。
  • i=4,j=1 として操作を行う。A=(5,6,4,6) になる。
  • i=4,j=3 として操作を行う。A=(5,6,5,5) になる。

3 回未満の操作で A の最小値と最大値の差を 1 以下にすることはできません。よって答えは 3 です。


入力例 2

1
313

出力例 2

0

入力例 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

出力例 3

2499999974

Score : 400 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

  • Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

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 as an integer.


Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

  • Choose i=2 and j=3 to make A=(4,6,4,7).
  • Choose i=4 and j=1 to make A=(5,6,4,6).
  • Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.


Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974
F - Distribution

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。

i\, (1 \leq i \leq N) 番目のすぬけ君は時刻 t に宝石をもらうと S_i 単位時間後、すなわち時刻 t+S_i にその宝石を (i+1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 T_i に i 番目のすぬけ君に宝石を渡します。

全ての i\, (1 \leq i \leq N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

  • 1 \leq N \leq 200000
  • 1 \leq S_i,T_i \leq 10^9
  • 入力は全て整数である。

入力

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

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

出力

N 行出力せよ。i\, (1 \leq i \leq N) 行目には、i 番目のすぬけ君が初めて宝石をもらう時刻を出力すること。


入力例 1

3
4 1 5
3 10 100

出力例 1

3
7
8

時刻 13 までのすぬけ君と高橋君の行動を時系列順に並べます。

時刻 3 : 高橋君が 1 番目のすぬけ君に宝石を渡します。

時刻 7 : 1 番目のすぬけ君が 2 番目のすぬけ君に宝石を渡します。

時刻 8 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 10 : 高橋君が 2 番目のすぬけ君に宝石を渡します。

時刻 11 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 13 : 3 番目のすぬけ君が 1 番目のすぬけ君に宝石を渡します。

時刻 14 以降も彼らは宝石の受け渡しを行いますが、答えには影響しません。


入力例 2

4
100 100 100 100
1 1 1 1

出力例 2

1
1
1
1

S_i や T_i が相異なるとは限らないことに注意してください。


入力例 3

4
1 2 3 4
1 2 4 7

出力例 3

1
2
4
7

あるすぬけくんが同時刻に複数の宝石の受け渡しをする可能性があること、特に高橋くんとすぬけくんの両方から同時に宝石を貰う可能性があることに注意してください。


入力例 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

出力例 4

50
22
63
28
44
60
64
27

Score : 300 points

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

  • 1 \leq N \leq 200000
  • 1 \leq S_i,T_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the time when Snuke i receives a gem for the first time.


Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.


Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.


Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.


Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27
G - Querying Multiset

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は何も書かれていないたくさんのボールと 1 つの袋を持っています。 最初、袋は空で、高橋君は Q 回の操作を行います。 それぞれの操作は以下の 3 種類のうちのいずれかです。

  • 操作 1 : まだ何も書かれていないボール 1 つに整数 X_i を書き込み、袋に入れる。
  • 操作 2 : 袋に入っているすべてのボールについて、そこに書かれている数を、それに X_i を加えたものに書き換える。
  • 操作 3 : 袋に入っているボールのうち書かれている数が最小のもの(複数ある場合はそのうちの 1 つ)を取り出し、そこに書かれている数を記録する。その後、そのボールを捨てる。

1\leq i\leq Q について i 回目の操作の種類 P_i および操作 1 , 2 における X_i の値が与えられるので、操作 3 において記録された数を順に出力してください。

制約

  • 1 \leq Q \leq 2\times 10^5
  • 1 \leq P_i \leq 3
  • 1 \leq X_i \leq 10^9
  • 入力は全て整数である。
  • P_i=3 であるような i が 1 つ以上存在する。
  • P_i=3 であるとき、 i 回目の操作の直前の時点で、袋には 1 つ以上のボールが入っている。

入力

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

Q
query_1
query_2
:
query_Q

2 行目から Q+1 行目の各 query_i は次のいずれかの形で与えられる。

1 X_i
2 X_i
3

まず、1\leq P_i\leq 3 が与えられる。これは操作の種類を表す。 P_i=1 または P_i=2 ならば、その後に空白区切りで X_i が与えられる。

出力

Q 回の操作のうち操作の種類が P_i=3 であるような各操作について、記録された数を改行区切りで出力せよ。


入力例 1

5
1 3
1 5
3
2 2
3

出力例 1

3
7

高橋君は次のように操作を行います。

  • 3 の書かれたボールを袋に入れる。
  • 5 の書かれたボールを袋に入れる。
  • 今、袋には 3 の書かれたボールと 5 の書かれたボールが入っているため、このうち小さい 3 の書かれたボールを取り出し、 3 を記録した後に捨てる。
  • 今、袋には 5 の書かれたボールのみが入っているため、この数を 5+2=7 に書き換える。
  • 今、袋には 7 の書かれたボールのみが入っているため、このボールを取り出し、 7 を記録した後に捨てる。

よって、記録された順に 3 , 7 を出力します。


入力例 2

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

出力例 2

5000000000

答えが 32 bit整数に収まらないことがある事に注意してください。

Score : 400 points

Problem Statement

Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do Q operations, each of which is of one of the following three types.

  • Type 1: Write an integer X_i on a blank ball and put it in the bag.
  • Type 2: For each ball in the bag, replace the integer written on it with that integer plus X_i.
  • Type 3: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.

For each 1\leq i\leq Q, you are given the type P_i of the i-th operation and the value of X_i if the operation is of Type 1 or 2. Print the integers recorded in the operations of Type 3 in order.

Constraints

  • 1 \leq Q \leq 2\times 10^5
  • 1 \leq P_i \leq 3
  • 1 \leq X_i \leq 10^9
  • All values in input are integers.
  • There is one or more i such that P_i=3.
  • If P_i=3, the bag contains at least one ball just before the i-th operation.

Input

Input is given from Standard Input in the following format:

Q
query_1
query_2
:
query_Q

Each query_i in the 2-nd through (Q+1)-th lines is in the following format:

1 X_i
2 X_i
3

The first number in each line is 1\leq P_i\leq 3, representing the type of the operation. If P_i=1 or P_i=2, it is followed by a space, and then by X_i.

Output

For each operation with P_i=3 among the Q operations, print the recorded integer in its own line.


Sample Input 1

5
1 3
1 5
3
2 2
3

Sample Output 1

3
7

Takahashi will do the following operations.

  • Write 3 on a ball and put it in the bag.
  • Write 5 on a ball and put it in the bag.
  • The bag now contains a ball with 3 and another with 5. Pick up the ball with the smaller of them, or 3. Record 3 and throw it away.
  • The bag now contains just a ball with 5. Replace this integer with 5+2=7.
  • The bag now contains just a ball with 7. Pick up this ball, record 7, and throw it away.

Therefore, we should print 3 and 7, in the order they are recorded.


Sample Input 2

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

Sample Output 2

5000000000

Note that the outputs may not fit into a 32-bit integer.

H - Transition Game

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。ここで、各 A_i (1\leq i\leq N) は 1\leq A_i \leq N をみたします。

高橋君と青木君が N 回ゲームを行います。i=1,2,\ldots,N 回目のゲームは次のようにして行われます。

  1. 青木君が正整数 K_i を指定する。
  2. 青木君の指定した K_i を聞いた後、高橋君は 1 以上 N 以下の整数 S_i を選び、黒板に書く。
  3. その後、 K_i 回次の操作を繰り返す。

    • 黒板に x が書かれているとき、それを消し、A_x を新しく書く。

K_i 回の操作の後で黒板に書かれている整数が i ならば i 回目のゲームは高橋君の勝ち、そうでないならば青木君の勝ちとなります。
ここで、K_i,S_i は i=1,2,\ldots,N に対して独立に選ぶ事ができます。

両者が、自身が勝つために最善の行動をとったとき、N 回のゲームのうち高橋君が勝つ回数を求めてください。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

両者が最善の行動をとったとき、N 回のゲームのうち高橋君が勝つ回数を出力せよ。


入力例 1

3
2 2 3

出力例 1

2

1 回目のゲームにおいて、青木君が K_1=2 を指定したとき、高橋君は S_1 として、1,2,3 のいずれを選んでも勝つことはできません。

例えば、高橋君が最初に黒板に S_1=1 と書いたとすると、2 回の操作で黒板に書かれている数は順に 1\to 2(=A_1) 、2\to 2(=A_2) と変化し、
最終的に黒板に書かれている数は 2(\neq 1) であるため、青木君の勝ちとなります。

一方、2,3 回目のゲームにおいては、青木君の指定した K_i の値によらず、高橋君はそれぞれ 2,3 を最初に黒板に書くことで勝つ事ができます。

よって、両者が、自分が勝つために最善の行動をとったとき、高橋君が勝つゲームは 2,3 回目の 2 回であるため、2 を出力します。


入力例 2

2
2 1

出力例 2

2

1 回目のゲームにおいて、高橋君は、青木君が指定した K_1 が奇数のときは 2、偶数のときは 1 を最初に黒板に書く事で勝つ事ができます。

同様に 2 回目のゲームにおいても勝つ方法が存在するため、1,2 回目のゲームのいずれでも高橋君は勝利する事ができ、2 が答えとなります。

Score : 500 points

Problem Statement

You are given a sequence of N numbers: A=(A_1,A_2,\ldots,A_N). Here, each A_i (1\leq i\leq N) satisfies 1\leq A_i \leq N.

Takahashi and Aoki will play N rounds of a game. For each i=1,2,\ldots,N, the i-th game will be played as follows.

  1. Aoki specifies a positive integer K_i.
  2. After knowing K_i Aoki has specified, Takahashi chooses an integer S_i between 1 and N, inclusive, and writes it on a blackboard.
  3. Repeat the following K_i times.

    • Replace the integer x written on the blackboard with A_x.

If i is written on the blackboard after the K_i iterations, Takahashi wins the i-th round; otherwise, Aoki wins.
Here, K_i and S_i can be chosen independently for each i=1,2,\ldots,N.

Find the number of rounds Takahashi wins if both players play optimally to win.

Constraints

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

Input

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

N
A_1 A_2 \ldots A_N

Output

Find the number of rounds Takahashi wins if both players play optimally to win.


Sample Input 1

3
2 2 3

Sample Output 1

2

In the first round, if Aoki specifies K_1=2, Takahashi cannot win whichever option he chooses for S_1: 1, 2, or 3.

For example, if Takahashi writes S_1=1 on the initial blackboard, the two operations will change this number as follows: 1\to 2(=A_1), 2\to 2(=A_2). The final number on the blackboard will be 2(\neq 1), so Aoki wins.

On the other hand, in the second and third rounds, Takahashi can win by writing 2 and 3, respectively, on the initial blackboard, whatever value Aoki specifies as K_i.

Therefore, if both players play optimally to win, Takashi wins two rounds: the second and the third. Thus, you should print 2.


Sample Input 2

2
2 1

Sample Output 2

2

In the first round, Takahashi can win by writing 2 on the initial blackboard if K_1 specified by Aoki is odd, and 1 if it is even.

Similarly, there is a way for Takahashi to win the second round. Thus, Takahashi can win both rounds: the answer is 2.

I - Cans and Openers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 個の品物があります。
これらはそれぞれ、缶切りが不要な缶・缶切りが必要な缶・缶切りのいずれかです。
i 個目の品物は、整数の組 (T_i, X_i) により次のように表されます。

  • T_i = 0 ならば、i 個目の品物は缶切りが不要な缶で、入手すると満足度 X_i を得る。
  • T_i = 1 ならば、i 個目の品物は缶切りが必要な缶で、入手した上で缶切りを使うと満足度 X_i を得る。
  • T_i = 2 ならば、i 個目の品物は缶切りで、X_i 個までの缶に対して使用できる。

N 個の品物から M 個を選んで入手するとき、得られる満足度の合計としてあり得る最大値を求めてください。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • T_i は 0,1,2 のいずれか
  • 1 \leq X_i \leq 10^9
  • 入力される値はすべて整数

入力

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

N M
T_1 X_1
T_2 X_2
\vdots
T_N X_N

出力

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


入力例 1

8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100

出力例 1

27

1, 2, 5, 7 個目の品物を入手し、7 個目の品物である缶切りを 5 個目の品物に対して使用すると、満足度 6 + 6 + 15 = 27 を得ます。
満足度が 28 以上になる品物の入手方法は存在しませんが、上記の例において 7 個目の品物のかわりに 6 個目の品物や 8 個目の品物を選んでも満足度 27 を得ることができます。


入力例 2

5 5
1 5
1 5
1 5
1 5
1 5

出力例 2

0

入力例 3

12 6
2 2
0 1
0 9
1 3
1 5
1 3
0 4
2 1
1 8
2 1
0 1
0 4

出力例 3

30

Score : 500 points

Problem Statement

There are N items.
Each of these is one of a pull-tab can, a regular can, or a can opener.
The i-th item is described by an integer pair (T_i, X_i) as follows:

  • If T_i = 0, the i-th item is a pull-tab can; if you obtain it, you get a happiness of X_i.
  • If T_i = 1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of X_i.
  • If T_i = 2, the i-th item is a can opener; it can be used against at most X_i cans.

Find the maximum total happiness that you get by obtaining M items out of N.

Constraints

  • 1 \leq M \leq N \leq 2 \times 10^5
  • T_i is 0, 1, or 2.
  • 1 \leq X_i \leq 10^9
  • All input values are integers.

Input

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

N M
T_1 X_1
T_2 X_2
\vdots
T_N X_N

Output

Print the answer as an integer.


Sample Input 1

8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100

Sample Output 1

27

If you obtain the 1-st, 2-nd, 5-th, and 7-th items, and use the 7-th item (a can opener) against the 5-th item, you will get a happiness of 6 + 6 + 15 = 27.
There are no ways to obtain items to get a happiness of 28 or greater, but you can still get a happiness of 27 by obtaining the 6-th or 8-th items instead of the 7-th in the combination above.


Sample Input 2

5 5
1 5
1 5
1 5
1 5
1 5

Sample Output 2

0

Sample Input 3

12 6
2 2
0 1
0 9
1 3
1 5
1 3
0 4
2 1
1 8
2 1
0 1
0 4

Sample Output 3

30