← 返回题目列表

AtCoder · joig2022_c

C. 投票

中文机器翻译题面 查看原题

配点: 100 点

問題文

在JOI高中,举行了一次投票,询问是否投票赞成或反对某个话题。N 学生轮流投票。在学生投票之前,他们可以看到其他学生的投票方式。 投票给

i 番目 (1 \leqq i \leqq N)的学生在满足以下条件时投“是”,在不满足以下条件时投“否”。

  • 最后一刻投票 X_i 学生,即。 在投票 i-1,i-2,...,i-X_i 的学生中,Y_i 超过一人投票“同意”。

但是, Y_i=0 ,无论其他学生的投票如何,都投“是”,Y_i=X_i+1 ,假设无论其他学生的投票如何,该学生都投了“反对”票。

给定每个学生投票的信息,编写一个程序来查找投票“赞成”的学生数量。

制約

  • 1 \leqq N \leqq 500\,000.
  • 0 \leqq X_i \leqq i-1 (1 \leqq i \leqq N).
  • 0 \leqq Y_i \leqq X_i+1 (1 \leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (28 点) N \leqq 3\,000.
  2. (32 点) X_i = i-1 (1 \leqq i \leqq N).
  3. (40 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

如果提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果,则该源代码将被识别为对于该子作业是正确的。

每次提交的分数是所提交源代码被认为正确的子任务分数的总和。

该作业的分数是此作业的所有提交内容的最高分。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入将以以下格式从标准输入给出。

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

投票“是”的学生人数显示在标准输出上。 1 行上。


入力例 1

4
0 1
1 0
1 1
3 3

出力例 1

2

投票如下: 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

5
0 0
1 1
2 3
3 1
4 3

出力例 2

4

此输入示例满足所有子任务约束。


入力例 3

10
0 0
1 2
1 1
1 0
3 1
2 3
1 1
5 3
8 4
7 2

出力例 3

4

此输入示例是一个小作业。 1,3 满足约束。 将