ABC466参加記

問題文
$N$ 個の選択肢があります。
あなたは、これらの中から $1$ つの選択肢を選びます。あなたが $i$ 番目の選択肢を選んだときの嬉しさは $X_i$ です。
どの選択肢を選んでも嬉しさが負になる場合は Yes を、そうでない場合は No を出力してください。

制約

• $2 \leq N \leq 10$
• $-100 \leq X_i \leq 100$
• 入力される値はすべて整数

入力
入力は以下の形式で標準入力から与えられる。
$N$
$X_1$ $X_2$ $\ldots$ $X_N$

出力
問題文中の指示に従って Yes、No のいずれかを出力せよ。

問題文
$N$ 個のボールがあります。
$i$ 番目のボールの色は $C_i$、大きさは $S_i$ です。ここで、色は $1, 2, \ldots, M$ の整数で表されます。
$k = 1, 2, \ldots, M$ について、色 $k$ のボールの大きさの最大値を出力してください。ただし、色 $k$ のボールが存在しない場合は -1 と出力してください。

制約

• $1 \leq N, M \leq 100$
• $1 \leq C_i \leq M$
• $1 \leq S_i \leq 100$
• 入力される値はすべて整数

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

$N$ $M$
$C_1$ $S_1$
$C_2$ $S_2$
$\vdots$
$C_N$ $S_N$

出力
$k = 1, 2, \ldots, M$ の順に、色 $k$ のボールが存在するならば色 $k$ のボールの大きさの最大値を、存在しないならば -1 を空白区切りで出力せよ。

問題文
この問題は インタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。
数直線上に、点 $1$, $2$, $\ldots$, $N$ が この順に 左から右に並んでいます。
最初、あなたには整数 $N$ のみが与えられます。
その後、あなたはジャッジに以下の質問を $\bm{2N}$ 回まで行うことができます。

• $1 \leq i \lt j \leq N$ を満たす整数 $i,j$ を選び、点 $i$ と点 $j$ の距離が $1$ 以下であるか質問する。
  

距離が $1$ 以下の $2$ 点組の個数、すなわち $1\leq i \lt j \leq N$ をみたす整数の組 $(i,j)$ であって、点 $i$ と点 $j$ の距離が $1$ 以下であるようなものの個数を出力してください。

制約

• $2 \leq N \leq 10^3$
• $N$ は整数

入出力
最初に、点の個数を表す整数 $N$ を標準入力から受け取ってください。

$N$

次に、あなたはジャッジに対して問題文中の質問を $2N$ 回まで繰り返すことができます。
質問は、以下の形式で標準出力に出力してください。 ここで、$i,j$ は $1 \leq i　\lt　j \leq N$ を満たす整数である必要があります。

? $i$ $j$

これに対する応答として、以下のどちらかが標準入力から与えられます。

Yes

No

ここで、Yes ならば点 $i$ と点 $j$ の距離が $1$ 以下であることを、No ならば点 $i$ と点 $j$ の距離が $1$ より大きいことを表します。
問題の答え $X$ が求まったら、解答を以下の形式で出力してください。 その後、ただちにプログラムを終了してください。

! $X$

問題文
$N$ 行 $N$ 列のマス目があります。
最初、マス目の上には何も置かれていません。
その状態から始めて、高橋君がマス目に対して $M$ 回の操作を順に行います。$i$ 回目 $(1\leq i\leq M)$ の操作は以下のとおりです。

• 上から $R_i$ 行目のマスに置かれているコマをすべて取り除く。
• 次に、左から $C_i$ 列目のマスに置かれているコマをすべて取り除く。
• 最後に、上から $R_i$ 行目かつ左から $C_i$ 列目のマスにコマを置く。 $M$ 回の操作の後でマス目に置かれているコマの個数を出力してください。

制約

• $1 \leq N \leq 3\times 10^5$
• $1 \leq M \leq 3\times 10^5$
• $1 \leq R_i \leq N$
• $1 \leq C_i \leq N$
• 入力はすべて整数

入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_M$ $C_M$

出力
$M$ 回の操作の後でマス目に置かれているコマの個数を出力せよ。

問題文
$N$ 枚のカードが並んでいます。カードには $1, 2, \ldots, N$ の番号が付けられています。
カード $i$ の表面には整数 $A_i$ が、裏面には整数 $B_i$ が書かれています。はじめ、すべてのカードは表面が上を向いています。
あなたは、以下の操作を高々 $K$ 回行うことができます。

• $1 \leq l \leq r \leq N$ なる整数 $l, r$ を選ぶ。$l \leq i \leq r$ なる各整数 $i$ について、カード $i$ を裏返す。ただし、カードを裏返すとは、操作を行う前に下を向いている面を上に向けることを指す。

操作を終えた後、各カードの上を向いている面に書かれている数の総和として考えられる最大値を求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10$
• $1 \leq A_i, B_i \leq 10^9$
• 入力される値はすべて整数

入力
入力は以下の形式で標準入力から与えられる。
$N$ $K$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力
答えを出力せよ。