No.2501 Maximum Inversion Number
タグ : / 解いたユーザー数 55
作問者 :
emthrm
torisasami4
rniya
Problem Statement
You are given positive integers $n, m$ and non-negative integer sequences $L = (L _ 1, L _ 2, \ldots, L _ n),\ R = (R _ 1, R _ 2, \ldots, R _ n)$ of length $n$.
A sequence $A = (A _ 1, A _ 2, \ldots, A _ m)$ of length $m$ is called a good sequence if it satisfies all of the following $2$ conditions.
- For all $i \in\lbrace 1, 2, \ldots, m\rbrace$, $A _ i$ is an integer between $1$ and $n$, inclusive.
- For all $x\in\lbrace 1, 2, \ldots, n\rbrace$, the number of $i \in\lbrace 1, 2, \ldots, m\rbrace$ satisfying $A _ i = x$ is at least $L _ x$ and at most $R _ x$.
Determine whether a good sequence exists, and if one exists, find the maximum possible inversion number of a good sequence.
Here, the inversion number of a sequence $A = (A _ 1, A _ 2, \ldots, A _ k)$ of length $k$ is defined as the number of integer pairs $(i, j)$ satisfying $1\leq i \lt j \leq k$ and $A _ i \gt A _ j$.
You are given $T$ test cases; solve the above problem for all of them.
Input
The input is given from Standard Input in the following format.
First, the number of test cases $T$ is given on line $1$ in the following format.
$T$
The $i\ (1\leq i\leq T)$-th test case is given on lines $3i - 1, 3i, 3i + 1$ in the following format.
$n\ m$
$\begin{matrix}
L _ 1 \ L _ 2 \ \cdots\ L _ n \newline
R _ 1 \ R _ 2 \ \cdots\ R _ n
\end{matrix}$
- All input values are integers.
- $1\leq T \leq 2\times 10 ^ 5$
- $1\leq n \leq 2\times 10 ^ 5$
- $1\leq m \leq 10 ^ 9$
- $0\leq L _ i \leq R _ i \leq 10 ^ 9$
- The sum of $n$ over the $T$ test cases is at most $2\times 10 ^ 5$.
Output
Print $T$ lines. On the $i\ (1\leq i\leq T)$-th line, for the $i$-th test case, print -1 if no good sequence exists; otherwise, print the maximum possible inversion number of a good sequence.
Also print a newline after the output on line $T$.
Sample
Sample 1
Input
3 3 3 0 0 2 0 2 3 3 4 1 2 3 4 5 6 2 1000000000 0 0 1000000000 1000000000
Output
2 -1 250000000000000000
-
About case 1
This input represents $n = 3,\ m = 3,\ L=(0,0,2),\ R=(0,2,3)$.
There are $4$ good sequences: $(2,3,3),(3,2,3),(3,3,2),(3,3,3)$, with inversion numbers $0,1,2,0$, respectively. Therefore, output $2$ as the answer.
-
About case 2
This input represents $n = 3,\ m = 4,\ L=(1,2,3),\ R=(4,5,6)$.
Not even $1$ good sequence exists, so print
-1. -
About case 3
The answer may not fit in a 32 bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。