CF397A.On Segment's Own Points

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Our old friend Alexey has finally entered the University of City N — the Berland capital. Alexey expected his father to get him a place to live in but his father said it was high time for Alexey to practice some financial independence. So, Alexey is living in a dorm.

The dorm has exactly one straight dryer — a 100 centimeter long rope to hang clothes on. The dryer has got a coordinate system installed: the leftmost end of the dryer has coordinate 0, and the opposite end has coordinate 100. Overall, the university has n students. Dean's office allows i-th student to use the segment (l__i, r__i) of the dryer. However, the dean's office actions are contradictory and now one part of the dryer can belong to multiple students!

Alexey don't like when someone touch his clothes. That's why he want make it impossible to someone clothes touch his ones. So Alexey wonders: what is the total length of the parts of the dryer that he may use in a such way that clothes of the others (n - 1) students aren't drying there. Help him! Note that Alexey, as the most respected student, has number 1.

我们的老朋友阿列克谢终于进入了城市 N 大学——即贝尔兰德的首都。阿列克谢本指望父亲为他安排一个住处,但父亲却表示:是时候让阿列克谢锻炼一下经济独立能力了。于是,阿列克谢住在了宿舍里。

宿舍里恰好只有一根笔直的晾衣绳——一条长度为 100 厘米的绳子,用于晾晒衣物。该晾衣绳上已安装了一个坐标系:绳子最左端坐标为 00,最右端坐标为 100100。整个大学共有 nn 名学生。教务处允许第 ii 名学生使用晾衣绳上的区间 (li, ri)(l_i,\,r_i)。然而,教务处的安排自相矛盾,导致晾衣绳的某些部分可能被多名学生同时分配!

阿列克谢不喜欢别人触碰他的衣物。因此,他希望确保自己的衣物与其他人的衣物完全不接触。于是阿列克谢想知道:在满足“其余 n−1n-1 名学生的衣物均不在此处晾晒”的前提下,他可使用的晾衣绳总长度是多少?请帮助他!注意:阿列克谢作为最受尊敬的学生,编号为 11。

输入格式

The first line contains a positive integer n (1 ≤ n ≤ 100). The (i + 1)-th line contains integers l__i and r__i (0 ≤ l__i < r__i ≤ 100) — the endpoints of the corresponding segment for the i-th student.

第一行包含一个正整数 nn(1≤n≤1001 \leq n \leq 100)。第 (i+1)(i + 1) 行包含两个整数 lil_i 和 rir_i(0≤li<ri≤1000 \leq l_i < r_i \leq 100)——表示第 ii 位学生的对应线段的端点。

输出格式

On a single line print a single number k, equal to the sum of lengths of the parts of the dryer which are inside Alexey's segment and are outside all other segments.

在一行中输出一个整数 kk,其值等于烘干机中位于阿列克谢线段内、且不位于其他任意线段内的部分的总长度。

输入输出样例

  • 输入#1

    3
    0 5
    2 8
    1 6

    输出#1

    1
  • 输入#2

    3
    0 10
    1 5
    7 15

    输出#2

    3

说明/提示

Note that it's not important are clothes drying on the touching segments (e.g. (0, 1) and (1, 2)) considered to be touching or not because you need to find the length of segments.

In the first test sample Alexey may use the only segment (0, 1). In such case his clothes will not touch clothes on the segments (1, 6) and (2, 8). The length of segment (0, 1) is 1.

In the second test sample Alexey may dry his clothes on segments (0, 1) and (5, 7). Overall length of these segments is 3.

注意:接触的线段上(例如 (0, 1) 和 (1, 2))是否认为衣物相互接触并不重要,因为你只需计算线段的总长度。

在第一个测试样例中,Alexey 只能使用线段 (0, 1)。此时,他的衣物不会与线段 (1, 6) 和 (2, 8) 上的衣物接触。线段 (0, 1) 的长度为 1。

在第二个测试样例中,Alexey 可以在线段 (0, 1) 和 (5, 7) 上晾晒衣物。这些线段的总长度为 3。

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

首页