TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1545
  • 题目
  • P1545Pugna看球赛
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Pugna最近在看一个足球联赛。只是现在一场比赛都没开始,Pugna想知道最终哪些球队可以夺冠。
    假设联赛采用淘汰赛的规则,就是一共n个球队以任意的顺序比赛,每场比赛都一定会角出胜负,负者直接淘汰。也就是说比赛n-1场之后就一定会出现冠军。
    现在Pugna给每个球队都标记了一个“战斗力”的范围,一场比赛中双方的战斗力都不会超出这个范围(可以等),并且战斗力强的队伍获胜。如果双方战斗力相同,则两个球队都可能获胜。注意每个球队的战斗力可能在每场比赛中都不一样。
    你的任务就是对于给定的n和所有的战斗力范围[Ai,Bi],求出所有可能夺冠的球队。

    输入格式

    第一行,一个整数n;
    接下来n行,每行两个整数Ai,Bi表示编号为i的球队战斗力范围;

    输出格式

    以升序输出所有可能夺冠的球队编号。一行一个。

    样例输入

    样例输入1:
    3
    1 1
    2 3
    3 4

    样例输入2:
    5
    1 5
    2 5
    3 6
    4 5
    999 9999

    样例输出

    样例输出1:
    2
    3

    样例输出2:
    5

    提示

    n<=10,0000
    -20,0000,0000<Ai<=Bi<20,0000,0000