跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#X261108C. 路灯检修

路灯检修

题目描述

一条道路长 LL 米,坐标 0,1,2,…,L0,1,2,\ldots,L 处各有一盏路灯。检修队给出 MM 个区间 [u,v][u,v],每个区间内的路灯都将被拆下,包括两个端点。

区间可以重叠。同一盏路灯即使出现在多个区间中,也只会被拆下一次。求全部检修结束后,还留在路上的路灯数量。

输入格式

第一行两个整数 L,ML,M。接下来 MM 行,每行两个整数 u,vu,v,表示一个检修区间。

输出格式

输出一个整数,表示剩余路灯数量。

数据范围与计分

1≤L≤1041\le L\le 10^4,1≤M≤1001\le M\le100,0≤u≤v≤L0\le u\le v\le L。

  • 基础部分:占总分的 60 分,保证所有检修区间两两没有公共整数坐标。
  • 完整部分:另占 40 分,满足上述完整数据范围。
  • 测试点独立计分,正确处理基础部分的全部测试点可获得 60 分;正确处理全部测试点可获得 100 分。

样例 1

10 2
1 5
3 7
4

样例说明

最初共有 11 盏路灯。拆下坐标 1 至 7 的路灯后,还剩坐标 0、8、9、10 处的 4 盏。

相关

在下列比赛中:

全栈考核