問題一覧 > 通常問題

No.2501 Maximum Inversion Number

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 55
作問者 : suisen / テスター : emthrm torisasami4 rniya
お気に入りにしたユーザー ProblemId : 9886 / 自分の提出
問題文最終更新日: 2023-09-11 16:00:42
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 408 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。