No.2667 Constrained Permutation
タグ : / 解いたユーザー数 41
作問者 :
cureskol
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もしくは右上の雲マークをクリックしてアカウントを作成してください。