E - Bib

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から N の番号がついた N 人の人がいます。

人 i は数 Q_i が書かれたゼッケンを着けており、人 P_i を見つめています。

i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数を、i=1,2,\ldots,N のそれぞれについて求めてください。

制約

  • 2 \leq N \leq 3\times 10^5
  • 1 \leq P_i \leq N
  • P_i は相異なる
  • 1 \leq Q_i \leq N
  • Q_i は相異なる
  • 入力は全て整数である

入力

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

N
P_1 P_2 \dots P_N
Q_1 Q_2 \dots Q_N

出力

i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数を S_i とする。
S_1,S_2,\ldots,S_N をこの順に空白区切りで出力せよ。


入力例 1

4
4 3 2 1
2 3 1 4

出力例 1

3 4 1 2

人 3 は 1 が書かれたゼッケンを着けており、人 3 が見つめている人 2 は 3 が書かれたゼッケンを着けています。 よって i=1 に対する答えは 3 になります。

図


入力例 2

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

出力例 2

4 8 6 5 3 10 9 2 1 7

Score : 300 points

Problem Statement

There are N people numbered from 1 to N.

Person i is wearing a bib with the number Q_i and is staring at person P_i.

For each i = 1,2,\ldots,N, find the number written on the bib of the person that the person wearing the bib with number i is staring at.

Constraints

  • 2 \leq N \leq 3\times 10^5
  • 1 \leq P_i \leq N
  • The values of P_i are distinct.
  • 1 \leq Q_i \leq N
  • The values of Q_i are distinct.
  • All input values are integers.

Input

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

N
P_1 P_2 \dots P_N
Q_1 Q_2 \dots Q_N

Output

Let S_i be the number written on the bib of the person that the person wearing the bib with number i is staring at.
Print S_1, S_2, \ldots, S_N in this order, separated by a single space.


Sample Input 1

4
4 3 2 1
2 3 1 4

Sample Output 1

3 4 1 2

Person 3 is wearing the bib with the number 1, and the person that person 3 is staring at, person 2, is wearing the bib with the number 3. Thus, the answer for i = 1 is 3.

Figure


Sample Input 2

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

Sample Output 2

4 8 6 5 3 10 9 2 1 7
F - Truck Driver

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 国には「トラック運転手は A 分以上運転する際には B 分以上の休憩を取らなければならない」というルールがあります。

a, b からなる長さ N の文字列 S と正整数 A,B が与えられます。以下の条件を全て満たす整数組 (l,r) の個数を求めてください。

  • 1\leq l \leq r \leq N
  • S の l 文字目から r 文字目までに含まれる a の個数が A 以上
  • S の l 文字目から r 文字目までに含まれる b の個数が B 未満

制約

  • 1\leq N \leq 3\times 10^5
  • 1 \leq A,B \leq N
  • S は a, b のみからなる長さ N の文字列
  • 与えられる数値は全て整数

入力

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

N A B
S

出力

答えを出力せよ。


入力例 1

11 4 2
abbaaabaaba

出力例 1

3

条件を満たす (l,r) の組は (4,8),(4,9),(5,9) の 3 個です。


入力例 2

13 1 2
bbbbbbbbbbbbb

出力例 2

0

条件を満たす (l,r) の組は存在しません。

Score : 300 points

Problem Statement

In AtCoder Country, there is a rule that "a truck driver must take a break of at least B minutes when driving for A minutes or more."

You are given a string S of length N consisting of a and b, and positive integers A and B. Find the number of integer pairs (l,r) that satisfy all of the following conditions.

  • 1\leq l \leq r \leq N
  • The number of a in the substring from the l-th character through the r-th character of S is greater than or equal to A.
  • The number of b in the substring from the l-th character through the r-th character of S is less than B.

Constraints

  • 1\leq N \leq 3\times 10^5
  • 1 \leq A,B \leq N
  • S is a string of length N consisting of a and b.
  • All input numbers are integers.

Input

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

N A B
S

Output

Print the answer.


Sample Input 1

11 4 2
abbaaabaaba

Sample Output 1

3

The pairs (l,r) that satisfy the conditions are (4,8),(4,9),(5,9), which is three pairs.


Sample Input 2

13 1 2
bbbbbbbbbbbbb

Sample Output 2

0

There are no pairs (l,r) that satisfy the conditions.

G - Medicines on Grid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

H 行 W 列のグリッドがあります。上から i 行目、左から j 列目のマス目を (i, j) と表します。各マスの状態は文字 A_{i,j} で表され、意味は以下の通りです。

  • . : 空きマス。
  • # : 障害物。
  • S : 空きマスかつスタート地点。
  • T : 空きマスかつゴール地点。

高橋君は、今いるマスから上下左右に隣り合う空きマスへ、エネルギーを 1 消費して移動することができます。ただし、エネルギーが 0 の状態で移動することはできず、またグリッドの外へ移動することはできません。

グリッドには合計で N 個の薬があります。i 番目の薬は空きマス (R_i, C_i) にあり、使うとエネルギーを E_i にすることができます。必ずしもエネルギーが増えるとは限らないことに注意してください。高橋君は自分のいるマスにある薬を使うことができます。使った薬はなくなります。

高橋君ははじめエネルギー 0 の状態でスタート地点にいて、ゴール地点まで移動したいです。これが可能かどうか判定してください。

制約

  • 1 \leq H, W \leq 200
  • A_{i, j} は ., #, S, T のいずれかである。
  • S と T は A_{i, j} にそれぞれちょうど 1 つ存在する。
  • 1 \leq N \leq 300
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W
  • i \neq j ならば (R_i, C_i) \neq (R_j, C_j)
  • A_{R_i, C_i} は # でない。
  • 1 \leq E_i \leq HW

入力

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

H W
A_{1, 1}A_{1, 2}\cdotsA_{1, W}
A_{2, 1}A_{2, 2}\cdotsA_{2, W}
\vdots
A_{H, 1}A_{H, 2}\cdotsA_{H, W}
N
R_1 C_1 E_1
R_2 C_2 E_2
\vdots
R_N C_N E_N

出力

高橋君がスタート地点からゴール地点へ移動することが可能なら Yes 、不可能なら No を出力せよ。


入力例 1

4 4
S...
#..#
#...
..#T
4
1 1 3
1 3 5
3 2 1
2 3 1

出力例 1

Yes

例えば、以下のようにしてゴール地点へ移動することができます。

  • 薬 1 を使う。エネルギーが 3 になる。
  • (1, 2) へ移動する。エネルギーが 2 になる。
  • (1, 3) へ移動する。エネルギーが 1 になる。
  • 薬 2 を使う。エネルギーが 5 になる。
  • (2, 3) へ移動する。エネルギーが 4 になる。
  • (3, 3) へ移動する。エネルギーが 3 になる。
  • (3, 4) へ移動する。エネルギーが 2 になる。
  • (4, 4) へ移動する。エネルギーが 1 になる。

この移動の途中には (2, 3) にも薬がありますが、これを使うとゴールできません。


入力例 2

2 2
S.
T.
1
1 2 4

出力例 2

No

高橋君はスタート地点から移動することができません。


入力例 3

4 5
..#..
.S##.
.##T.
.....
3
3 1 5
1 2 3
2 2 1

出力例 3

Yes

Score: 425 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left. The state of each cell is represented by the character A_{i,j}, which means the following:

  • .: An empty cell.
  • #: An obstacle.
  • S: An empty cell and the start point.
  • T: An empty cell and the goal point.

Takahashi can move from his current cell to a vertically or horizontally adjacent empty cell by consuming 1 energy. He cannot move if his energy is 0, nor can he exit the grid.

There are N medicines in the grid. The i-th medicine is at the empty cell (R_i, C_i) and can be used to set the energy to E_i. Note that the energy does not necessarily increase. He can use the medicine in his current cell. The used medicine will disappear.

Takahashi starts at the start point with 0 energy and wants to reach the goal point. Determine if this is possible.

Constraints

  • 1 \leq H, W \leq 200
  • A_{i, j} is one of ., #, S, and T.
  • Each of S and T exists exactly once in A_{i, j}.
  • 1 \leq N \leq 300
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W
  • (R_i, C_i) \neq (R_j, C_j) if i \neq j.
  • A_{R_i, C_i} is not #.
  • 1 \leq E_i \leq HW

Input

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

H W
A_{1, 1}A_{1, 2}\cdotsA_{1, W}
A_{2, 1}A_{2, 2}\cdotsA_{2, W}
\vdots
A_{H, 1}A_{H, 2}\cdotsA_{H, W}
N
R_1 C_1 E_1
R_2 C_2 E_2
\vdots
R_N C_N E_N

Output

If Takahashi can reach the goal point from the start point, print Yes; otherwise, print No.


Sample Input 1

4 4
S...
#..#
#...
..#T
4
1 1 3
1 3 5
3 2 1
2 3 1

Sample Output 1

Yes

For example, he can reach the goal point as follows:

  • Use medicine 1. Energy becomes 3.
  • Move to (1, 2). Energy becomes 2.
  • Move to (1, 3). Energy becomes 1.
  • Use medicine 2. Energy becomes 5.
  • Move to (2, 3). Energy becomes 4.
  • Move to (3, 3). Energy becomes 3.
  • Move to (3, 4). Energy becomes 2.
  • Move to (4, 4). Energy becomes 1.

There is also medicine at (2, 3) along the way, but using it will prevent him from reaching the goal.


Sample Input 2

2 2
S.
T.
1
1 2 4

Sample Output 2

No

Takahashi cannot move from the start point.


Sample Input 3

4 5
..#..
.S##.
.##T.
.....
3
3 1 5
1 2 3
2 2 1

Sample Output 3

Yes
H - GCD of Subset

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) と N 以下の正整数 K が与えられます。
i=1,2,\dots,N について次の問題を解いてください。

  • A_i を含むように K 個の要素を A から選ぶ時、それらの最大公約数 (GCD) としてあり得る最大値を求めてください。

制約

  • 1 \leq K \leq N \leq 1.2 \times 10^6
  • 1 \leq A_i \leq 10^6
  • 入力される値は全て整数

入力

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

N K
A_1 A_2 \dots A_N

出力

N 行出力せよ。j 行目には i=j の時の答えを出力せよ。


入力例 1

5 2
3 4 6 7 12

出力例 1

3
4
6
1
6

i=1 の時は A_1 と A_3 を選ぶと最大公約数が \gcd(\lbrace 3, 6 \rbrace) = 3 となり、これが最大です。
i=2 の時は A_2 と A_5 を選ぶと最大公約数が \gcd(\lbrace 4, 12 \rbrace) = 4 となり、これが最大です。
i=3 の時は A_3 と A_5 を選ぶと最大公約数が \gcd(\lbrace 6, 12 \rbrace) = 6 となり、これが最大です。
i=4 の時は A_4 と A_2 を選ぶと最大公約数が \gcd(\lbrace 7, 4 \rbrace) = 1 となり、これが最大です。
i=5 の時は A_5 と A_3 を選ぶと最大公約数が \gcd(\lbrace 12, 6 \rbrace) = 6 となり、これが最大です。


入力例 2

3 3
6 10 15

出力例 2

1
1
1

入力例 3

10 3
414003 854320 485570 52740 833292 625990 909680 885153 435420 221663

出力例 3

59
590
590
879
879
590
20
879
590
59

Score : 475 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and a positive integer K (at most N).
For each i = 1, 2, \dots, N, solve the following problem:

  • When you choose K elements from A that include A_i, find the maximum possible GCD (greatest common divisor) of those chosen elements.

Constraints

  • 1 \leq K \leq N \leq 1.2 \times 10^6
  • 1 \leq A_i \leq 10^6
  • All input values are integers.

Input

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

N K
A_1 A_2 \dots A_N

Output

Print N lines. The j-th line should contain the answer for i=j.


Sample Input 1

5 2
3 4 6 7 12

Sample Output 1

3
4
6
1
6

For i=1, choosing A_1 and A_3 yields \gcd(\lbrace 3,6 \rbrace) = 3, which is the maximum.
For i=2, choosing A_2 and A_5 yields \gcd(\lbrace 4,12 \rbrace) = 4, which is the maximum.
For i=3, choosing A_3 and A_5 yields \gcd(\lbrace 6,12 \rbrace) = 6, which is the maximum.
For i=4, choosing A_4 and A_2 yields \gcd(\lbrace 7,4 \rbrace) = 1, which is the maximum.
For i=5, choosing A_5 and A_3 yields \gcd(\lbrace 12,6 \rbrace) = 6, which is the maximum.


Sample Input 2

3 3
6 10 15

Sample Output 2

1
1
1

Sample Input 3

10 3
414003 854320 485570 52740 833292 625990 909680 885153 435420 221663

Sample Output 3

59
590
590
879
879
590
20
879
590
59
I - Vacation Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

0, 1 からなる長さ N の文字列 S が与えられます。S の i 文字目を S_i とします。

Q 個のクエリを与えられた順に処理してください。
クエリは 3 個の整数の組 (c, L, R) で表されて、c の値によってクエリの種類が異なります。

  • c=1 のとき : L \leq i \leq R を満たす整数 i について、S_i が 1 ならば 0 に、0 ならば 1 に変更する。
  • c=2 のとき : S の L 文字目から R 文字目までを取り出して出来る文字列を T とする。T に含まれる連続する 1 の長さの最大値を出力する。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 10^5
  • S は長さ N の 0, 1 からなる文字列
  • c \in \lbrace 1, 2 \rbrace
  • 1 \leq L \leq R \leq N
  • N, Q, c, L, R は全て整数

入力

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

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

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

c L R

出力

c=2 であるクエリの個数を k として、k 行出力せよ。
i 行目には i 番目の c=2 であるクエリに対する答えを出力せよ。


入力例 1

7 6
1101110
2 1 7
2 2 4
1 3 6
2 5 6
1 4 7
2 1 7

出力例 1

3
1
0
7

クエリを順に処理すると次のようになります。

  • はじめ、S= 1101110 です。
  • 1 番目のクエリについて、T = 1101110 です。T に含まれる連続する 1 の中で最も長いものは、T の 4 文字目から 6 文字目からなる 111 なので、答えは 3 になります。
  • 2 番目のクエリについて、T = 101 です。T に含まれる連続する 1 の中で最も長いものは、T の 1 文字目あるいは 3 文字目の 1 なので、答えは 1 になります。
  • 3 番目のクエリについて、操作後の S は 1110000 です。
  • 4 番目のクエリについて、T = 00 です。T に 1 は含まれないので答えは 0 になります。
  • 5 番目のクエリについて、操作後の S は 1111111 です。
  • 6 番目のクエリについて、T = 1111111 です。T に含まれる連続する 1 の中で最も長いものは、T の 1 文字目から 7 文字目からなる 1111111 なので、答えは 7 になります。

Score : 550 points

Problem Statement

You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.

Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.

  • When c=1: For each integer i such that L \leq i \leq R, if S_i is 1, change it to 0; if it is 0, change it to 1.
  • When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive 1s in T.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 10^5
  • S is a string of length N consisting of 0 and 1.
  • c \in \lbrace 1, 2 \rbrace
  • 1 \leq L \leq R \leq N
  • N, Q, c, L, and R are all integers.

Input

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

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

c L R

Output

Let k be the number of queries with c=2. Print k lines.
The i-th line should contain the answer to the i-th query with c=2.


Sample Input 1

7 6
1101110
2 1 7
2 2 4
1 3 6
2 5 6
1 4 7
2 1 7

Sample Output 1

3
1
0
7

The queries are processed as follows.

  • Initially, S= 1101110.
  • For the first query, T = 1101110. The longest sequence of consecutive 1s in T is 111 from the 4-th character to 6-th character, so the answer is 3.
  • For the second query, T = 101. The longest sequence of consecutive 1s in T is 1 at the 1-st or 3-rd character, so the answer is 1.
  • For the third query, the operation changes S to 1110000.
  • For the fourth query, T = 00. T does not contain 1, so the answer is 0.
  • For the fifth query, the operation changes S to 1111111.
  • For the sixth query, T = 1111111. The longest sequence of consecutive 1s in T is 1111111 from the 1-st to 7-th characters, so the answer is 7.