CF137C.History

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Polycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.

Everybody knows that the World history encompasses exactly n events: the i-th event had continued from the year a__i to the year b__i inclusive (a__i < b__i). Polycarpus easily learned the dates when each of n events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event j includes an event i if a__j < a__i and b__i < b__j. Your task is simpler: find the number of events that are included in some other event.

波利卡普斯非常喜欢在学校学习,而且他总是认真完成家庭作业。波利卡普斯在自然科学方面从未遇到过困难,因为他的高祖是一位伟大的物理学家——赛因斯坦。然而,他在历史学科上却一直不太顺利。

众所周知,世界历史恰好包含 nn 个事件:其中第 ii 个事件从年份 aia_i 持续到年份 bib_i(含端点),即 ai<bia_i < b_i。波利卡普斯轻松记住了这 nn 个事件各自的起止年份(他从高祖那里继承了极佳的记忆力)。但老师给他布置了一项更复杂的任务:波利卡普斯不仅要熟记所有事件的起止时间,还需判断每个事件是否被另一个事件所包含。老师认为:若事件 jj 包含事件 ii,当且仅当 aj<aia_j < a_i 且 bi<bjb_i < b_j。而你的任务则更简单:请计算有多少个事件被至少另一个事件所包含。

输入格式

The first input line contains integer n (1 ≤ n ≤ 105) which represents the number of events. Next n lines contain descriptions of the historical events, one event per line. The i + 1 line contains two integers a__i and b__i (1 ≤ a__i < b__i ≤ 109) — the beginning and the end of the i-th event. No two events start or finish in the same year, that is, a__i ≠ a__j, a__i ≠ b__j, b__i ≠ a__j, b__i ≠ b__j for all i, j (where i ≠ j). Events are given in arbitrary order.

第一行输入包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5),表示事件的数量。接下来的 nn 行每行描述一个历史事件,第 i+1i+1 行包含两个整数 aia_i 和 bib_i(1≤ai<bi≤1091 \leq a_i < b_i \leq 10^9),分别表示第 ii 个事件的起始年份和结束年份。任意两个事件的起始年份或结束年份均不相同,即对所有 i,ji, j(其中 i≠ji \neq j)均有:ai≠aja_i \neq a_j、ai≠bja_i \neq b_j、bi≠ajb_i \neq a_j、bi≠bjb_i \neq b_j。事件以任意顺序给出。

输出格式

Print the only integer — the answer to the problem.

输出唯一的整数——该问题的答案。

输入输出样例

  • 输入#1

    5
    1 10
    2 9
    3 8
    4 7
    5 6

    输出#1

    4
  • 输入#2

    5
    1 100
    2 50
    51 99
    52 98
    10 60

    输出#2

    4
  • 输入#3

    1
    1 1000000000

    输出#3

    0

说明/提示

In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third — in the second and the second — in the first.

In the second example all events except the first one are contained in the first.

In the third example only one event, so the answer is 0.

在第一个例子中,第五个事件包含在第四个事件中;类似地,第四个事件包含在第三个事件中,第三个事件包含在第二个事件中,第二个事件包含在第一个事件中。

在第二个例子中,除第一个事件外,其余所有事件均包含在第一个事件中。

在第三个例子中,仅有一个事件,因此答案为 0。

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

首页