题目详情题解（0）讨论（0）提交记录（0）

AT_abc408_c.[ABC408C] Not All Covered

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

AtCoder 国度有 NN 堵城墙和 MM 个炮塔。第 ii 个炮塔守卫着第 LiL_i 到第 RiR_i 堵城墙。

求至少摧毁多少个炮塔，使得至少一堵城墙没有被任何一个瞭望塔守卫。

输入格式

第一行两个整数 N,M(1≤N≤106,1≤M≤2×105)N,M(1\le N\le 10^6,1\le M\le 2\times 10^5)。
接下来 MM 行，每行两个整数 Li,Ri(1≤Li≤Ri≤N)L_i,R_i(1\le L_i\le R_i\le N)。

输出格式

一行一个整数表示答案。

输入输出样例

  • 输入#1

    10 4
1 6
4 5
5 10
7 10

    输出#1

    1

  • 输入#2

    5 2
1 2
3 4

    输出#2

    0

  • 输入#3

    5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3

    输出#3

    3

说明/提示

样例 1 解释

摧毁炮塔 11 后，城墙 33 无炮塔守卫。不摧毁炮塔时任何城墙均有炮塔守卫，故答案为 11。

样例 2 解释

没有炮塔守卫城墙 55，你不需要摧毁任何炮塔。故答案为 00。

By @chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页