AT_abc440_d.[ABC440D] Forbidden List 2

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个由 $N$ 个不同整数组成的列表。列表中第 $i$ 个（ $1 \leq i \leq N$ ）整数是 $A_i$ 。

给你 $Q$ 个问题，请逐一回答。第 $j$ 个问题（ $1 \leq j \leq Q$ ）如下：

在大于或等于 $X_j$ 的不在列表中的最小的 $Y_j$ 个整数中，找出第 $Y_j$ 个整数。

输入格式

输入内容由标准输入法提供，格式如下：

$N$ $Q\\$
$A_1$ $\cdots$ $A_N\\$
$X_1$ $Y_1\\$
$\vdots\\$
$X_Q$ $Y_Q\\$

输出格式

输出 $Q$ 行。第 $j$ 行（ $1 \leq j \leq Q$ ）应该包含对第 $j$ 个问题的回答。

输入输出样例

输入#1

5 4
16 9 2 3 1
6 10
12 4
1 1
1000000000 1000000000

输出#1

输入#2

10 10
284008711 658403910 982178205 50598815 694147827 230009803 763277509 509451676 821970166 284008710
740250292 159734720
255870361 8400028
23659634 718117163
697334729 301140741
698853172 270344164
713418715 285312509
50065000 52368934
46642556 591869945
607623561 273664826
482426028 265015448

输出#2

说明/提示

样例解释 #1

对于第一个问题，大于或等于 $6$ 的最小的 $10$ 个不在列表中的整数是 $6,\ 7,\ 8,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15,\ 17$ 。因此，问题的答案是 $17$ 。

对于第二个问题，大于或等于 $12$ 的最小的 $4$ 个整数，不在列表中的是 $12,\ 13,\ 14,\ 15$ 。因此，问题的答案是 $15$ 。

对于第三个问题，在大于或等于 $1$ 的整数中，不在列表中的第 $1$ 个数是 $4$ 。

对于第四题，在大于或等于 $1,000,000,000$ 的整数中，不在列表中的第 $1,000,000,000$ 个数是 $1,999,999,999$ 。

数据范围

$1 \leq N \leq 3 \times 10^5$
$1 \leq Q \leq 3 \times 10^5$
$1 \leq A_i \leq 10^9$ ( $1 \leq i \leq N$ )
$A_1, \dots, A_N$ 互不相同。
$1 \leq X_j \leq 10^9$ ( $1 \leq j \leq Q$ )
$1 \leq Y_j \leq 10^9$ ( $1 \leq j \leq Q$ )
所有输入值均为整数。

输入解题思路，AI测评打分。不知道怎么写?

首页