AT_joig2022_c.投票 (Voting)

在 JOI 高中，针对某个议题进行了“赞成”或“反对”的投票，共有 $N$ 名学生依次进行投票。每位学生在投票前，可以知道此前所有学生的投票结果。

第 $i$ 位（$1 \leq i \leq N$）投票的学生，满足以下条件时会投“赞成”，否则投“反对”：

• 在他之前投票的 $X_i$ 名学生，即第 $i-1, i-2, \ldots, i-X_i$ 位学生中，至少有 $Y_i$ 人投了“赞成”。

此外，若 $Y_i=0$，则无论其他学生如何投票，该学生都会投“赞成”；若 $Y_i=X_i+1$，则无论其他学生如何投票，该学生都会投“反对”。

给定每位学生的投票信息，请编写程序，求出投“赞成”的学生人数。

输入以以下格式从标准输入读入：

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

请输出投“赞成”的学生人数，输出一行。

限制条件

• $1 \leq N \leq 500\,000$。
• $0 \leq X_i \leq i-1$（$1 \leq i \leq N$）。
• $0 \leq Y_i \leq X_i+1$（$1 \leq i \leq N$）。
• 输入的所有数值均为整数。

子任务

1.（28 分）$N \leq 3\,000$。
2.（32 分）$X_i = i-1$（$1 \leq i \leq N$）。
3.（40 分）无额外限制。

评分说明

所有提交将在评测系统上进行评分。

提交的源代码在对应子任务的所有评测输入数据上均输出正确结果时，该子任务判为正确。

每次提交的得分为该提交在所有子任务中获得的分数之和。

本题的得分为所有提交中得分的最大值。

当前得分可在“提交结果”标签页的“我的得分情况”中查看。

样例解释 1

投票依次由以下 4 名学生进行：

1. 第 1 位学生，$Y_1 = X_1 + 1$，因此投“反对”。
2. 第 2 位学生，$Y_2 = 0$，因此投“赞成”。
3. 在他之前投票的 $X_3(=1)$ 名学生中，有 $1$ 人投了“赞成”，达到 $Y_3(=1)$，因此第 3 位学生投“赞成”。
4. 在他之前投票的 $X_4(=3)$ 名学生中，有 $2$ 人投了“赞成”，未达到 $Y_4(=3)$，因此第 4 位学生投“反对”。

投“赞成”的学生有 $2$ 人。因此输出 $2$。

该输入样例满足子任务 $1,3$ 的限制。

样例解释 2

该输入样例满足所有子任务的限制。

样例解释 3

该输入样例满足子任务 $1,3$ 的限制。

由 ChatGPT 4.1 翻译