問題一覧 > 通常問題

No.2667 Constrained Permutation

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 41
作問者 : suisen / テスター : cureskol ygussany Shirotsume
お気に入りにしたユーザー ProblemId : 10301 / 自分の提出
問題文最終更新日: 2024-02-29 19:45:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 420 (順位表) の他の問題:

Problem Statement

You are given $n$ pairs of integers $(l _ 1, r _ 1),(l _ 2,r _ 2),\ldots,(l _ n, r _ n)$.

Find the number of integers $k$ that satisfy the following (Condition).

$\quad$(Condition): There exists a sequence $P=(P _ 1, P _ 2, \ldots, P _ n)$ obtained by rearranging $(1,2,\ldots,n)$ such that $l _ i \leq k + P _ i \leq r _ i$ holds for all $i=1,2,\ldots,n$.

It can be proved that, under the constraints of this problem, the number of integers $k$ satisfying the (Condition) is less than $2 ^ {31}$.

Input

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

$n$
$l _ 1\ r _ 1$
$l _ 2\ r _ 2$
$\vdots$
$l _ n\ r _ n$
  • All input values are integers.
  • $1\leq n\leq 2\times 10 ^ 5$
  • $1\leq l _ i\leq r _ i\leq 10 ^ 9$

Output

Print the number of integers $k$ satisfying the (Condition) on $1$ line, followed by a newline.

Sample

Sample 1
Input
4
2 3
3 6
3 4
1 5
Output
3

The input represents $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)$.

When $k = 2$, if we set $P = (1,4,2,3)$, then $l _ i \leq k + P _ i \leq r _ i$ indeed holds for all $i=1,2,\ldots,n$, as shown below.

  • For $i=1$, $2 \leq 2 + 1 \leq 3$
  • For $i=2$, $3 \leq 2 + 4 \leq 6$
  • For $i=3$, $3 \leq 2 + 2 \leq 4$
  • For $i=4$, $1 \leq 2 + 3 \leq 5$

In addition, $k = 0, 1$ satisfy the (Condition), and it can be proved that no other $k$ satisfies the (Condition). Therefore, the answer for this input is $3$.

Sample 2
Input
3
1 2
1 2
1 2
Output
0

There is no integer $k$ satisfying the (Condition).

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