logo AlgoBeat OnlineJudge
登录 注册

#215506. [COCI 2025/2026 #5] 剪刀 / Škare

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

本题满分


为了把使用剪刀的技能练到极致,Fran 想出了一个新的训练方法。

他有一条长度为 厘米的纸条和一把剪刀,并请 Lana 给他下达切割指令。

Lana 会给 Fran 共 条指令,每条形如:“把第 条纸条在距离左端 厘米处剪开”。

一开始 Fran 只有一条纸条。第一次剪开后会得到两段:长度分别为 。此后每次剪开某一段纸条时,新产生的两段会替换原来那一段,并保持在序列中的位置。

更形式化地:设当前共有 条纸条,长度依次为 。若 Lana 让他把第 条剪在 厘米处,则新序列变为:

完成所有切割后,他们想验证过程是否正确,其中一种方式是统计最终序列中有多少种不同的纸条长度。请你计算这个数量。

输入格式

第一行包含两个自然数 ),表示原始纸条长度与指令条数。

接下来 行每行包含两个自然数 ,且 ,其中 为当时第 条纸条的长度),表示把当时从左到右数第 条纸条在 厘米处剪开。

输出格式

输出一行一个整数,表示完成所有切割后,最终剩下的纸条有多少种不同的长度。

样例

样例输入 1

5 1
1 2

样例输出 1

2

样例输入 2

6 2
1 4
1 2

样例输出 2

1

样例输入 3

10 3
1 2
2 3
3 2

样例输出 3

2

数据范围与提示

【样例解释】

样例 #1 解释:

样例 #2 解释:

样例 #3 解释:

【子任务】

子任务 分值 限制
对所有
对所有
无额外限制