P3641 [APIO2016] Maximum Gap

## 评测方式 以下是本题评测方式，与题面不符时以这里为准。 你的代码中不应该包含 `gap.h` 库。 你的代码中需如下进行 `findGap` 和 `MinMax` 函数的声明： ```cpp extern "C" void MinMax(long long,long long,long long*,long long*); extern "C" long long findGap(int,int); ``` [spj 与交互库](https://www.luogu.com.cn/paste/c4olee2x) 不保证没锅，要是有锅请私信供题人然后 D 死他。

There are $N$ strictly increasing nonnegative integers $a_1, a_2, \dots, a_N$ with $0 \leq a_1 < a_2 < \cdots < a_N \leq 10^{18}$. You need to find the maximum value among $a_{i + 1} - a_i$ for $1 \leq i \leq N - 1$. Your program cannot read this integer sequence directly, but you can query information about the sequence through the provided function. Please refer to the implementation details below for your language. You must implement a function that returns the maximum value of $a_{i + 1} - a_i$ for $1 \leq i \leq N - 1$. Judging method The following judging method applies. If this differs from the main statement, this section prevails. - Your code must not include the gap.h library. - You must declare the functions findGap and MinMax as follows: ```cpp extern "C" void MinMax(long long,long long,long long*,long long*); extern "C" long long findGap(int,int); ``` - [spj and interaction library](https://www.luogu.com.cn/paste/c4olee2x) - If you encounter issues, please contact the problem provider. Implementation details This problem only supports C++ (including cpp11, cpp14, cpp17). You must implement a function findGap(T, N), which takes the following parameters and returns a value of type long long: - $T$: subtask ID ($1$ or $2$). - $N$: the length of the sequence. Your function findGap may call the system-provided query function MinMax(s, t, &mn, &mx). The first two parameters $s$ and $t$ are of type long long, and the last two parameters &mn and &mx are pointers to long long (mn and mx are long long variables). When MinMax(s, t, &mn, &mx) returns, mn will store the minimum $a_i$ such that $a_i \in [s, t]$, and mx will store the maximum $a_i$ such that $a_i \in [s, t]$. If there is no number from the sequence in the interval $[s, t]$, both mn and mx will be set to $-1$. You must ensure $s \leq t$ when querying; otherwise, the program will terminate and the test will receive a score of $0$. Sample 1 C/C++ Consider $N = 4, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 8$. The answer should be $3$, which can be obtained using the following queries to MinMax: - Call MinMax(1, 2, &mn, &mx), then both mn and mx return $2$. - Call MinMax(3, 7, &mn, &mx), then mn returns $3$, and mx returns $6$. - Call MinMax(8, 9, &mn, &mx), then both mn and mx return $8$. Sample judging method The sample judge reads two lines from standard input. The first line contains two integers, the subtask ID $T$ and the sequence length $N$. The second line contains $N$ strictly increasing nonnegative integers. Then the program writes two lines to standard output: the first line is the return value of findGap, and the second line is the value of the cost $M$. The following input describes the sample above: ```plane 2 4 2 3 6 8 ``` Note that the actual interaction library and spj encrypt the testdata. Constraints and agreements For all test cases, $2 \leq N \leq 100000$. Before each test case starts, $M$ will be initialized to $0$. Subtask 1 (30 points): Each call to MinMax increases $M$ by $1$. To receive full points, you must ensure $M \leq \frac{N + 1}{2}$ for all test cases in this subtask. Subtask 2 (70 points): Let $k$ be the number of sequence elements within the interval $[s, t]$ for a MinMax call. Each call to MinMax increases $M$ by $k + 1$. For each test case, if $M \leq 3N$, you will receive 70 points; otherwise, you will receive $\dfrac{60}{\sqrt{\frac MN + 1} - 1}$ points. Your score for this subtask is the minimum over all its test cases.

## 样例一 ### C/C++ 考虑 $N = 4, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 8$。 则答案应该是 $3$，可以通过下面的几组对 `MinMax` 的询问获得： 调用 `MinMax(1, 2, &mn, &mx)`，则 `mn` 和 `mx` 皆返回 $2$。 调用 `MinMax(3, 7, &mn, &mx)`，则 `mn` 返回 $3$，`mx` 返回 $6$。 调用 `MinMax(8, 9, &mn, &mx)`，则 `mn` 和 `mx` 皆返回 $8$。 ### Pascal 考虑 $N = 4, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 8$。 则答案应该是 $3$，可以通过下面的几组对 `MinMax` 的询问获得： 调用 `MinMax(1, 2, mn, mx)`，则 `mn` 和 `mx` 皆返回 $2$。 调用 `MinMax(3, 7, mn, mx)`，则 `mn` 返回 $3$，`mx` 返回 $6$。 调用 `MinMax(8, 9, mn, mx)`，则 `mn` 和 `mx` 皆返回 $8$。 ## 样例评测方式 样例测评系统从标准输入中读入两行。第一行包含两个整数，子任务编号 $T$，和序列长度 $N$。第二行包含 $N$ 个严格递增的非负整数。然后该程序会向标准输出中写入两行，第一行为 `findGap` 的返回值，第二行为花费 $M$ 的值。 下面的输入描述了上面的样例： ```plane 2 4 2 3 6 8 ``` 注意实际使用的交互库和 spj 对数据进行了加密。

N/A

Translated by ChatGPT 5