E - Reorder Cards

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

H 行 W 列の格子状に HW 枚のカードが並べられています。
i=1,\ldots,N について、上から A_i 行目、左から B_i 列目にあるカードには数 i が書かれており、それ以外の HW-N 枚のカードには何も書かれていません。

これらのカードに対し、以下の 2 種類の操作を可能な限り繰り返します。

  • 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
  • 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める

操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

  • 1 \leq H,W \leq 10^9
  • 1 \leq N \leq \min(10^5,HW)
  • 1 \leq A_i \leq H
  • 1 \leq B_i \leq W
  • (A_i,B_i) は相異なる
  • 入力に含まれる値は全て整数である

入力

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

H W N
A_1 B_1
\vdots
A_N B_N

出力

N 行出力せよ。

操作終了後に数 i が書かれたカードが上から C_i 行目、左から D_i 列目に存在するとき、i 行目には C_i,D_i をこの順に空白区切りで出力せよ。


入力例 1

4 5 2
3 2
2 5

出力例 1

2 1
1 2

何も書かれていないカードを * で表すことにします。最初、カードの配置は以下の通りです。

*****
****2
*1***
*****

操作終了後、カードの配置は以下の通りになります。

*2
1*

1 が書かれたカードは上から 2 行目、左から 1 列目にあり、2 が書かれたカードは上から 1 行目、左から 2 列目にあります。


入力例 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

出力例 2

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

Score : 300 points

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

  • If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
  • If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

  • 1 \leq H,W \leq 10^9
  • 1 \leq N \leq \min(10^5,HW)
  • 1 \leq A_i \leq H
  • 1 \leq B_i \leq W
  • All pairs (A_i,B_i) are distinct.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W N
A_1 B_1
\vdots
A_N B_N

Output

Print N lines.

If, after the end of the process, the card with the number i is at the C_i-th row from the top and D_i-th column from the left, the i-th line should contain C_i and D_i in this order with a space between them.


Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.


Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
F - Choose Elements

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N),B=(B_1,\ldots,B_N) が与えられます。

以下の条件を全て満たす長さ N の数列 X=(X_1,\ldots,X_N) が存在するかを判定してください。

  • すべての i(1\leq i\leq N) について、X_i = A_i または X_i = B_i

  • すべての i(1\leq i\leq N-1) について、|X_i - X_{i+1}| \leq K

制約

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq K \leq 10^9
  • 1 \leq A_i,B_i \leq 10^9
  • 入力は全て整数である

入力

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

N K
A_1 \ldots A_N
B_1 \ldots B_N

出力

条件を全て満たす X が存在するならば Yes と、存在しないならば No と出力せよ。


入力例 1

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

出力例 1

Yes

X=(9,6,3,7,5) が全ての条件を満たします。


入力例 2

4 90
1 1 1 100
1 2 3 100

出力例 2

No

条件を満たす X は存在しません。


入力例 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

出力例 3

Yes

Score : 300 points

Problem Statement

You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.

  • X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).

  • |X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).

Constraints

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

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N
B_1 \ldots B_N

Output

If there is an X that satisfies all of the conditions, print Yes; otherwise, print No.


Sample Input 1

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

Sample Output 1

Yes

X=(9,6,3,7,5) satisfies all conditions.


Sample Input 2

4 90
1 1 1 100
1 2 3 100

Sample Output 2

No

No X satisfies all conditions.


Sample Input 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Sample Output 3

Yes
G - Cylinder

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

空の筒があります。Q 個のクエリが与えられるので順に処理してください。
クエリは次の 2 種類のいずれかです。

  • 1 x c:数 x が書かれたボールを筒の右側から c 個入れる
  • 2 c:筒の左側からボールを c 個取り出し、取り出したボールに書かれている数の合計を出力する

なお、筒の中でボールの順序が入れ替わることはないものとします。

制約

  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq x \leq 10^9
  • 1 \leq c \leq 10^9
  • 2 c のクエリが与えられるとき、筒の中には c 個以上のボールがある
  • 入力に含まれる値は全て整数である

入力

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

Q
{\rm query}_1
\vdots
{\rm query}_Q

i 番目のクエリを表す {\rm query}_i は以下の 2 種類のいずれかである。

1 x c
2 c

出力

2 c のクエリに対する答えを順に改行区切りで出力せよ。


入力例 1

4
1 2 3
2 2
1 3 4
2 3

出力例 1

4
8
  • 1 番目のクエリでは、2 が書かれたボールを筒の右側から 3 個入れます。
    筒の中のボールに書かれた数は左から順に (2,2,2) となります。
  • 2 番目のクエリでは、筒の左側からボールを 2 個取り出します。
    取り出されたボールに書かれている数はそれぞれ 2,2 であり、合計は 4 であるため、これを出力します。 筒の中のボールに書かれた数は左から順に (2) となります。
  • 3 番目のクエリでは、3 が書かれたボールを筒の右側から 4 個入れます。
    筒の中のボールに書かれた数は左から順に (2,3,3,3,3) となります。
  • 4 番目のクエリでは、筒の左側からボールを 3 個取り出します。
    取り出されたボールに書かれている数はそれぞれ 2,3,3 であり、合計は 8 であるため、これを出力します。 筒の中のボールに書かれた数は左から順に (3,3) となります。

入力例 2

2
1 1000000000 1000000000
2 1000000000

出力例 2

1000000000000000000

入力例 3

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

出力例 3


出力するものがないこともあります。

Score : 400 points

Problem Statement

We have a horizontal cylinder. Given Q queries, process them in the given order.
Each query is of one of the following two types.

  • 1 x c: Insert c balls, with a number x written on each of them, to the right end of the cylinder.
  • 2 c: Take out the c leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.

We assume that the balls do never change their order in the cylinder.

Constraints

  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq x \leq 10^9
  • 1 \leq c \leq 10^9
  • Whenever a query of type 2 c is given, there are c or more balls in the cylinder.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

Q
{\rm query}_1
\vdots
{\rm query}_Q

The i-th query {\rm query}_i is in one of the following two formats.

1 x c
2 c

Output

Print the response to the queries of type 2 c in the given order, with newlines in between.


Sample Input 1

4
1 2 3
2 2
1 3 4
2 3

Sample Output 1

4
8
  • For the 1-st query, insert 3 balls, with a number 2 written on each of them, to the right end of the cylinder.
    The cylinder has now balls with numbers (2,2,2) written on them, from left to right.
  • For the 2-nd query, take out the 2 leftmost balls contained in the cylinder.
    The numbers written on the balls taken out are 2,2, for a sum of 4, which should be printed. The cylinder has now a ball with a number (2) written on it, from left to right.
  • For the 3-rd query, insert 4 balls, with a number 3 written on each of them, to the right end of the cylinder.
    The cylinder has now balls with numbers (2,3,3,3,3) written on them, from left to right.
  • For the 4-th query, take out the 3 leftmost balls contained in the cylinder.
    The numbers written on the balls taken out are 2,3,3, for a sum of 8, which should be printed. The cylinder has now balls with numbers (3,3) written on them, from left to right.

Sample Input 2

2
1 1000000000 1000000000
2 1000000000

Sample Output 2

1000000000000000000

Sample Input 3

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

Sample Output 3


There may be nothing you should print.

H - Palindromic Shortest Path

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 頂点の有向グラフがあり、頂点には 1, 2, \ldots, N の番号が付いています。

辺の情報は N^2 個の文字 C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N} によって与えられます。ここで、C_{i, j} は英小文字あるいは - です。

C_{i, j} が英小文字のとき頂点 i から頂点 j へ向かう辺がちょうど 1 つ存在してラベル C_{i, j} が付いており、C_{i, j} が - のとき頂点 i から頂点 j へ向かう辺は存在しません。

1 \leq i, j \leq N を満たす各整数組 (i, j) について、以下の問題に対する答えを求めてください。

  • 頂点 i から頂点 j に向かう(単純とは限らない)パスのうち、辺に付けられたラベルの文字を順に結合した文字列が回文となるようなものの中で最も短いものの長さを求めよ。ただし、そのようなパスがない場合は答えは -1 とせよ。

制約

  • 1 \leq N \leq 100
  • N は整数
  • C_{i, j} は英小文字あるいは -

入力

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

N
C_{1, 1}C_{1, 2}\ldotsC_{1, N}
C_{2, 1}C_{2, 2}\ldotsC_{2, N}
\vdots
C_{N, 1}C_{N, 2}\ldotsC_{N, N}

出力

整数組 (i, j) に対する答えを A_{i, j} として以下の形式で出力せよ。

A_{1, 1} A_{1, 2} \ldots A_{1, N}
A_{2, 1} A_{2, 2} \ldots A_{2, N}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}

入力例 1

4
ab--
--b-
---a
c---

出力例 1

0 1 2 4
-1 0 1 -1
3 -1 0 1
1 -1 -1 0

例として (i, j) = (1, 4) の場合について説明します。

頂点 1 \to 1 \to 2 \to 3 \to 4 というパスにおける辺に付けられた文字のラベルを順に結合すると文字列 abba が得られます。これは回文であり、頂点 1 から頂点 4 へ向かう長さ 3 以下のパスであって辺に付けられたラベルの文字を順に結合した文字列が回文となるものは存在しないため (i, j) = (1, 4) に対する答えは 4 となります。

空文字列も回文であることに注意してください。


入力例 2

5
us---
-st--
--s--
u--s-
---ts

出力例 2

0 1 3 -1 -1
-1 0 1 -1 -1
-1 -1 0 -1 -1
1 3 -1 0 -1
-1 -1 5 1 0

Score : 450 points

Problem Statement

We have a directed graph with N vertices, numbered 1, 2, \ldots, N.

Information about the edges is given by N^2 characters C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N}. Here, each C_{i, j} is either a lowercase English letter or -.

If C_{i, j} is a lowercase English letter, then there is exactly one directed edge from vertex i to vertex j labeled C_{i, j}. If C_{i, j} is -, there is no edge from vertex i to vertex j.

For each integer pair (i, j) with 1 \leq i, j \leq N, answer the following question:

  • Among all (not necessarily simple) paths from vertex i to vertex j whose concatenation of labels on the edges forms a palindrome, what is the length of the shortest such path? If there is no such path, the answer is -1.

Constraints

  • 1 \leq N \leq 100
  • N is an integer.
  • Each C_{i, j} is either a lowercase English letter or -.

Input

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

N
C_{1, 1}C_{1, 2}\ldotsC_{1, N}
C_{2, 1}C_{2, 2}\ldotsC_{2, N}
\vdots
C_{N, 1}C_{N, 2}\ldotsC_{N, N}

Output

Let A_{i, j} be the answer to the question for the pair (i, j). Print them in the following format:

A_{1, 1} A_{1, 2} \ldots A_{1, N}
A_{2, 1} A_{2, 2} \ldots A_{2, N}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}

Sample Input 1

4
ab--
--b-
---a
c---

Sample Output 1

0 1 2 4
-1 0 1 -1
3 -1 0 1
1 -1 -1 0

For example, consider the case (i, j) = (1, 4).
By taking the path 1 \to 1 \to 2 \to 3 \to 4, and concatenating the labels on its edges in order, we get the string abba, which is a palindrome.
There is no path of length at most 3 from vertex 1 to vertex 4 whose concatenation of labels is a palindrome. Thus, the answer for (1, 4) is 4.

Note that the empty string is also a palindrome.


Sample Input 2

5
us---
-st--
--s--
u--s-
---ts

Sample Output 2

0 1 3 -1 -1
-1 0 1 -1 -1
-1 -1 0 -1 -1
1 3 -1 0 -1
-1 -1 5 1 0
I - Cumulative Cumulative Cumulative Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N,Q および A=(A_1,\ldots,A_N) が与えられます。
以下のクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。

  • 1 x v : A_x を v に更新する。
  • 2 x : B_i=\sum_{j=1}^{i}A_j、C_i=\sum_{j=1}^{i}B_j、D_i=\sum_{j=1}^{i}C_j としたときの D_x を \bmod\ 998244353 で出力する。

制約

  • 1 \leq N \leq 2\times10^5
  • 1 \leq Q \leq 2\times10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq x \leq N
  • 0 \leq v \leq 10^9
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。ここで {\rm query}_i は i 番目に処理するクエリである。

N Q
A_1 A_2 \ldots A_N
{\rm query}_1
{\rm query}_2
\vdots
{\rm query}_Q

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 x v
2 x

出力

クエリへの答えを改行区切りで出力せよ。


入力例 1

3 3
1 2 3
2 3
1 2 0
2 3

出力例 1

15
9

1 番目のクエリの時点で A=(1,2,3) であるため、B=(1,3,6)、C=(1,4,10)、D=(1,5,15) となり、D_3=15 です。

3 番目のクエリの時点で A=(1,0,3) であるため、B=(1,1,4)、C=(1,2,6)、D=(1,3,9) となり、D_3=9 です。


入力例 2

2 1
998244353 998244353
2 1

出力例 2

0

Score : 500 points

Problem Statement

You are given N, Q, and A=(A_1,\ldots,A_N).
Process Q queries, each of which is of one of the following two kinds:

  • 1 x v: update A_x to v.
  • 2 x: let B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j, and D_i=\sum_{j=1}^{i}C_j. Print D_x modulo 998244353.

Constraints

  • 1 \leq N \leq 2\times10^5
  • 1 \leq Q \leq 2\times10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq x \leq N
  • 0 \leq v \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format, where {\rm query}_i denotes the i-th query to be processed:

N Q
A_1 A_2 \ldots A_N
{\rm query}_1
{\rm query}_2
\vdots
{\rm query}_Q

Each query is given in one of the following two formats:

1 x v
2 x

Output

Print the answer to the queries, with newlines in between.


Sample Input 1

3 3
1 2 3
2 3
1 2 0
2 3

Sample Output 1

15
9

When the 1-st query is given, A=(1,2,3), so B=(1,3,6), C=(1,4,10), and D=(1,5,15); thus, D_3=15.

When the 3-rd query is given, A=(1,0,3), so B=(1,1,4), C=(1,2,6), and D=(1,3,9); thus, D_3=9.


Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0