問題一覧 > 通常問題

No.2667 Constrained Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : suisensuisen / テスター : cureskolcureskol ygussanyygussany ShirotsumeShirotsume
3 ProblemId : 10301 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-29 19:45:45

問題文

$n$ 個の整数組 $(l _ 1, r _ 1),(l _ 2,r _ 2),\ldots,(l _ n, r _ n)$ が与えられます。

次の (条件) を満たす整数 $k$ の個数を求めてください。
$\quad$(条件): $(1,2,\ldots,n)$ を並べ替えて得られる数列 $P=(P _ 1, P _ 2, \ldots, P _ n)$ であって、全ての $i=1,2,\ldots,n$ に対して $l _ i \leq k + P _ i \leq r _ i$ が成り立つようなものが存在する。

なお、本問題の制約下において、(条件) を満たす整数 $k$ の個数は $2 ^ {31}$ 未満であることを証明できます。

入力

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

$n$
$l _ 1\ r _ 1$
$l _ 2\ r _ 2$
$\vdots$
$l _ n\ r _ n$
  • 入力は全て整数で与えられる。
  • $1\leq n\leq 2\times 10 ^ 5$
  • $1\leq l _ i\leq r _ i\leq 10 ^ 9$

出力

(条件) を満たす整数 $k$ の個数を $1$ 行に出力して改行してください。

サンプル

サンプル1
入力
4
2 3
3 6
3 4
1 5
出力
3

入力は $n = 4,\ (l _ 1, r _ 1) = (2, 3),\ (l _ 2, r _ 2) = (3, 6),\ (l _ 3, r _ 3) = (3, 4),\ (l _ 4, r _ 4) = (1, 5)$ を表します。

$k = 2$ のとき、$P = (1,4,2,3)$ と定めれば、次に示すように確かに全ての $i=1,2,\ldots,n$ に対して $l _ i \leq k + P _ i \leq r _ i$ が成り立っています。

  • $i=1$ に対して、$2 \leq 2 + 1 \leq 3$
  • $i=2$ に対して、$3 \leq 2 + 4 \leq 6$
  • $i=3$ に対して、$3 \leq 2 + 2 \leq 4$
  • $i=4$ に対して、$1 \leq 2 + 3 \leq 5$

他に $k = 0, 1$ が (条件) を満たしますが、それ以外の $k$ は (条件) を満たさないことを証明できます。従って、この入力に対する答えは $3$ となります。

サンプル2
入力
3
1 2
1 2
1 2
出力
0

(条件) を満たす整数 $k$ は存在しません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。