ABC477参加記

問題文

ある信号機の色は B（青）、Y（黄）、R（赤）、B（青）、Y（黄）、R（赤）$\dots$ という順に、周期的に変化します。

現在の信号機の色を表す文字 $c$ が与えられます。次の信号機の色を出力してください。

制約

• $c$ は B、Y、R のいずれか

入力

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

$c$

出力

次の信号機の色を表す文字を出力せよ。

問題文

数直線上に $N$ 人の人がいます。人には $1$ から $N$ までの番号がついており、人 $i$ は座標 $X_i$ にいます。ただし、同じ座標に複数の人がいる場合もあります。

ある人が「一線を画す」とは、自分以外のどの人との距離も $D$ 以上であることをいいます。

厳密には、人 $i$ が「一線を画す」とは、 すべての $j ~ (1 \leq j \leq N,\ j \neq i)$ に対して $|X_i-X_j| \geq D$ が成り立つことをいいます。

「一線を画す」人の番号をすべて昇順に出力してください。

制約

• $2 \le N \le 100$
• $1 \le D \le 10^9$
• $1 \le X_i \le 10^9$
• 入力される値は全て整数

入力

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

$N$ $D$
$X_1$ $X_2$ $\dots$ $X_N$

出力

一線を画す人の人数を $K$、その人たちの番号を昇順に並べた列を $(P_1,P_2,\dots,P_K)$ とする。以下の形式で出力せよ。

$K$
$P_1$ $P_2$ $\dots$ $P_K$

ただし $K=0$ の場合、$2$ 行目は空行とせよ。

問題文

文字列 $S, T$ が与えられます。 $Q$ 個のクエリを処理してください。 クエリでは $L, R$ が与えられるので、$S$ の $L$ 文字目から $R$ 文字目までからなる部分文字列に、$T$ が部分文字列として含まれるかを判定してください。

部分文字列とは
$S$ の部分文字列とは、$S$ の先頭から $0$ 文字以上、末尾から $0$ 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。

制約

• $S$ は長さ $1$ 以上 $4 \times 10^5$ 以下の英小文字からなる文字列
• $T$ は長さ $1$ 以上 $10$ 以下の英小文字からなる文字列
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L \leq R \leq |S|$
• $Q, L, R$ は整数

入力

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

$Q$
$S$
$T$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

各クエリ $\mathrm{query}_q$ は以下の形式で与えられる。

$L$ $R$

出力

$Q$ 行出力せよ。$q$ 行目には $q$ 番目のクエリについて、$S$ の $L$ 文字目から $R$ 文字目までからなる部分文字列に、$T$ が部分文字列として含まれれば Yes を、含まれなければ No を出力せよ。

問題文

$N$ 個のマスが横一列に並んでおり、左から順にマス $1$ からマス $N$ までの番号がついています。色は英小文字で表されます。

はじめ、すべてのマスの色は a で、各マスには何も置かれていません。

$Q$ 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の $2$ 種類のいずれかです。

• 1 X : マス $X$ にタイルが置かれていなければタイルを置き、置かれていれば取り除く。

• 2 C : タイルが置かれていないすべてのマスの色を $C$ に変更する。

すべてのクエリを処理した後の各マスの色を（タイルが置かれているかどうかにかかわらず）求めてください。

制約

• $1 \le N,Q \le 3\times 10^5$
• 各クエリはタイプ $1$ またはタイプ $2$ のいずれか
• タイプ $1$ のクエリにおいて、$X$ は $1 \le X \le N$ を満たす整数
• タイプ $2$ のクエリにおいて、$C$ は英小文字 $1$ 文字

入力

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

$N$ $Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

各クエリ $\mathrm{query}_i ~ (1 \le i \le Q)$ は

$1$ $X$

または、

$2$ $C$

の形で与えられる。

出力

最終的な各マスの色を、左から順につなげた長さ $N$ の文字列として出力せよ。

問題文

頂点に $1$ から $N+1$ の番号がついた $N+1$ 頂点の辺重み付き無向グラフが与えられます。 $1 \leq i \leq N$ を満たす整数 $i$ について、頂点 $i$ と頂点 $(i \bmod N) + 1$ を結ぶ重み $A_i$ の辺があります。 また、$1 \leq i \leq N$ を満たす整数 $i$ について、頂点 $i$ と頂点 $N+1$ を結ぶ重み $B_i$ の辺があります。これ以外の辺はありません。

$Q$ 個のクエリを処理してください。クエリでは $S, T$ が与えられるので、頂点 $S$ から頂点 $T$ への最短経路の長さを求めてください。

制約

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^9$
• $1 \leq S \lt T \leq N+1$
• 入力される値は全て整数

入力

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

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

各クエリ $\mathrm{query}_q$ は以下の形式で与えられる。

$S$ $T$

出力

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

問題文

$N$ 行 $M$ 列のグリッドが与えられます。上から $i$ 行目では、左から $L_i$ 列目から $R_i$ 列目までのマスが黒く塗られており、それ以外のマスは白く塗られています。

$Q$ 個のクエリが与えられます。各クエリでは、以下の問題に答えてください。

• 整数 $A,B,C,D$ が与えられます。上から $A$ 行目から $B$ 行目まで、左から $C$ 列目から $D$ 列目までの長方形領域に含まれる黒いマスの個数を求めてください。

制約

• $1 \le N,M,Q \le 2\times10^5$
• $1 \le L_i \le R_i \le M$
• 各クエリについて、$1 \le A \le B \le N$
• 各クエリについて、$1 \le C \le D \le M$
• 入力される値はすべて整数

入力

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

$N$ $M$ $Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

各クエリ $\mathrm{query}_i ~ (1 \le i \le Q)$ は

$A$ $B$ $C$ $D$

の形で与えられる。

出力

$Q$ 行出力せよ。$i$ 行目には、$i$ 番目のクエリに対する答えを出力せよ。

問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点の木が与えられます。$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。また、頂点 $i$ には整数 $x_i$ が書かれています。 $Q$ 個のクエリを処理してください。クエリでは整数 $s,t,a,b$ が与えられるので、以下の条件を満たす整数 $y$ の個数を求めてください。

• 頂点 $s$ と頂点 $t$ を結ぶパス上にある頂点のうち、整数 $y$ が書かれた頂点の個数を $f$ とする。この時、$a \leq f \leq b$ が成り立つ。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq u_i \lt v_i \leq N$
• 入力で与えられるグラフは木
• $1 \leq x_i \leq N$
• $1 \leq s \lt t \leq N$
• $1 \leq a \leq b \leq N$
• 入力される値は全て整数

入力

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

$N$ $Q$
$x_1$ $x_2$ $\dots$ $x_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N - 1}$ $v_{N - 1}$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

各クエリ $\mathrm{query}_q$ は以下の形式で与えられる。

$s$ $t$ $a$ $b$

出力

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