AdditionalFile5131.zip

#5131. 「JOI Open 2025」抽奖

标签: 交互 | 时间限制: 5000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI Open 2025 T2 「くじ引き / Lottery」

JOI 君正在策划一场抽奖大会。在这场大会中，将使用偶数个袋子。每个袋子最初装有若干红球和蓝球（可能为 $0$ 个）。抽奖大会持续进行，直到某个袋子变空为止。参加抽奖大会的人，每次从每个袋子中各抽取一个球。最后，若抽取的红球和蓝球数量相等，则可以获得 $1$ 个奖品。参加者抽取的球不会放回袋中。

JOI 君为抽奖大会准备了 $N$ 个袋子，编号从 $0$ 到 $N-1$。袋子 $i$ $(0 \leq i \leq N-1)$ 内有 $X_{i}$ 个红球和 $Y_{i}$ 个蓝球。

在抽奖大会中，计划从这 $N$ 个袋子中选择若干个使用。有 $Q$ 种选择方案，第 $j$ $(1 \leq j \leq Q)$ 种方案是使用袋子 $L_{j}, L_{j}+1, \ldots, R_{j}$。其中，$R_{j} - L_{j} + 1$ 是偶数。

JOI 君为了准备抽奖大会的奖品，想知道每种方案下，参加者可能获得的奖品总数最大值是多少。给定袋子的信息和选择方案的内容，你需要编写一个程序，计算每种方案下参加者可能获得的奖品总数的最大值。

实现细节

你需要提交一个文件，文件名为 lottery.cpp。该程序必须通过 #include 预处理器指令包含 lottery.h，并实现以下函数：

• $\texttt{void init(int N, int Q, std::vector<int> X, std::vector<int> Y)}$

  • 此函数在开始时仅调用一次。
  • 参数 $\texttt{N}$ 是 JOI 君准备的袋子数量 $N$。
  • 参数 $\texttt{Q}$ 是袋子选择方案的数量 $Q$。
  • 参数 $\texttt{X}$ 是一个长度为 $N$ 的数组，$\texttt{X[i]}$ $(0 \leq i \leq N-1)$ 表示袋子 $i$ 中的红球数量。
  • 参数 $\texttt{Y}$ 是一个长度为 $N$ 的数组，$\texttt{Y[i]}$ $(0 \leq i \leq N-1)$ 表示袋子 $i$ 中的蓝球数量。

• \texttt{int max_prize(int L, int R)}

  • 此函数在 $\texttt{init}$ 函数调用后被调用 $Q$ 次。
  • 对于第 $j$ $(1 \leq j \leq Q)$ 次调用：
    • 参数 $\texttt{L}$ 是第 $j$ 个方案中的 $L_{j}$ 值。
    • 参数 $\texttt{R}$ 是第 $j$ 个方案中的 $R_{j}$ 值。
    • 此函数必须返回第 $j$ 个方案下参加者可能获得的奖品总数最大值。

• 内部使用的其他函数或全局变量可以自由实现。

• 你的程序不得以任何方式与标准输入、标准输出或其他文件进行交互，但允许向标准错误输出调试信息。

编译与运行

用于测试你程序的评测程序示例包含在可以从「文件」中下载的压缩包中。该归档文件也包含需提交的文件样例。

评测程序示例由一个文件组成，文件名为 grader.cpp。要测试你的程序，请将 grader.cpp, lottery.cpp, lottery.h 放入同一目录，并执行以下命令：

g++ -std=gnu++20 -O2 -o grader grader.cpp lottery.cpp

或者，你可以使用压缩包中包含的 compile.sh 文件，执行以下命令：

./compile.sh

编译成功后，将生成名为 grader 的可执行文件。

注意，实际评测程序与评测程序示例可能不同。评测程序示例作为单一进程启动，从标准输入读取输入，并将结果输出到标准输出。

输入格式

评测程序示例从标准输入读取以下格式的数据：

第一行包含两个整数 $N, Q$。

第二行包含 $N$ 个整数 $X_{0}, X_{1}, \ldots, X_{N-1}$。

第三行包含 $N$ 个整数 $Y_{0}, Y_{1}, \ldots, Y_{N-1}$。

接下来 $Q$ 行，第 $j$ $(1 \leq j \leq Q)$ 行包含两个整数 $L_{j}, R_{j}$。

输出格式

评测程序示例在每次调用 \texttt{max_prize} 函数时，将其返回值按顺序在标准输出中输出一行。

样例 1

输入

5 3
2 1 3 1 0
1 1 0 2 0
0 3
1 4
2 3

输出

2
0
2

调用	返回值
$\texttt{init(5, 3, [2, 1, 3, 1, 0], [1, 1, 0, 2, 0])}$
\texttt{max_prize(0, 3)}	$\texttt{2}$
\texttt{max_prize(1, 4)}	$\texttt{0}$
\texttt{max_prize(2, 3)}	$\texttt{2}$

第 $1$ 次 \texttt{max_prize} 调用使用袋子 $0, 1, 2, 3$。若参加者按以下方式抽球，则获得的奖品总数为 $2$：

• 第 $1$ 个参加者从袋子 $0, 1, 2, 3$ 分别抽取红球、蓝球、红球、蓝球。抽取的红球和蓝球数量相等，因此获得 $1$ 个奖品。
• 第 $2$ 个参加者从袋子 $0, 1, 2, 3$ 分别抽取蓝球、红球、红球、蓝球。抽取的红球和蓝球数量相等，因此获得 $1$ 个奖品。
• 此时袋子 $1$ 已空，抽奖大会结束。

参加者无法获得 $3$ 个以上奖品。因此，第 $1$ 次 \texttt{max_prize} 调用应返回 $2$。

第 $2$ 次 \texttt{max_prize} 调用使用袋子 $1, 2, 3, 4$。由于袋子 $4$ 最初为空，参加者无法抽取任何球，抽奖大会立即结束。因此，第 $2$ 次 \texttt{max_prize} 调用应返回 $0$。

第 $3$ 次 \texttt{max_prize} 调用使用袋子 $2, 3$。若参加者按以下方式抽球，则获得的奖品总数为 $2$：

• 第 $1$ 个参加者从袋子 $2, 3$ 分别抽取红球、红球。抽取的红球和蓝球数量不等，因此未获得奖品。
• 第 $2$ 个参加者从袋子 $2, 3$ 分别抽取红球、蓝球。抽取的红球和蓝球数量相等，因此获得 $1$ 个奖品。
• 第 $3$ 个参加者从袋子 $2, 3$ 分别抽取红球、蓝球。抽取的红球和蓝球数量相等，因此获得 $1$ 个奖品。
• 此时袋子 $2, 3$ 已空，抽奖大会结束。

参加者无法获得 $3$ 个以上奖品。因此，第 $3$ 次 \texttt{max_prize} 调用应返回 $2$。

这个样例满足子任务 $1, 2, 4, 5, 6$ 的限制。

样例 2

输入

6 5
1 3 3 2 1 0
1 2 1 1 2 1
0 1
1 2
1 4
2 5
4 5

输出

2
3
3
1
1

调用	返回值
$\texttt{init(6, 5, [1, 3, 3, 2, 1, 0], [1, 2, 1, 1, 2, 1])}$
\texttt{max_prize(0, 1)}	$\texttt{2}$
\texttt{max_prize(1, 2)}	$\texttt{3}$
\texttt{max_prize(1, 4)}	$\texttt{3}$
\texttt{max_prize(2, 5)}	$\texttt{1}$
\texttt{max_prize(4, 5)}	$\texttt{1}$

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 200000$
• $1 \leq Q \leq 500000$
• $0 \leq X_{i} \leq 10^{9}$ $(0 \leq i \leq N-1)$
• $0 \leq Y_{i} \leq 10^{9}$ $(0 \leq i \leq N-1)$
• $0 \leq L_{j} < R_{j} \leq N-1$ $(1 \leq j \leq Q)$
• $R_{j} - L_{j} + 1$ $(1 \leq j \leq Q)$ 是偶数
• 输入值均为整数。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$16$	$Q \leq 100$, $X_{i} \leq 100$, $Y_{i} \leq 100$ $(0 \leq i \leq N-1)$，$R_{j} - L_{j} + 1 \leq 100$ $(1 \leq j \leq Q)$
$2$	$16$	$Q \leq 100$, $R_{j} - L_{j} + 1 \leq 100$ $(1 \leq j \leq Q)$
$3$	$19$	$Q \leq 200000$, $L_{j} \leq L_{j+1}$, $R_{j} \leq R_{j+1}$ $(1 \leq j \leq Q-1)$
$4$	$12$	$N \leq 20000$, $Q \leq 50000$
$5$	$14$	$N \leq 100000$, $Q \leq 200000$
$6$	$23$	无附加限制