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

C. 路灯检修

  • 传统题
  • 2000ms
  • 256MiB

路灯检修

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一条道路长 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 盏。

全栈考核

未参加
状态
已结束
规则
IOI
题目
7
开始于
2026-11-8 19:00
结束于
2026-11-8 21:30
持续时间
2.5 小时
主持人
参赛人数
6