CF4D.Mysterious Present

提高+/省选-

通过率:0%

AC君温馨提醒

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

题目描述

Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes AA = { a1,a2,...,ana_{1},a_{2},...,a_{n} }, where the width and the height of the ii -th envelope is strictly higher than the width and the height of the (i1)(i-1) -th envelope respectively. Chain size is the number of envelopes in the chain.

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes.

Peter has very many envelopes and very little time, this hard task is entrusted to you.

给出一个限制 (w,h)(w,h)nn 个物品的二维信息(wi,hi)(w_i,h_i)

求物品二维都满足 wi>w,hi>hw_i>w,h_i>h 的前提下的最长二维严格上升子序列以及其长度(wi>wi1,hi>hi1(w_i>w_{i-1},h_i > h_{i-1} )

如果找不到任何一个物品满足条件 只需输出一行 0

输入格式

The first line contains integers nn , ww , hh ( 1<=n<=50001<=n<=5000 , 1<=w,h<=1061<=w,h<=10^{6} ) — amount of envelopes Peter has, the card width and height respectively. Then there follow nn lines, each of them contains two integer numbers wiw_{i} and hih_{i} — width and height of the ii -th envelope ( 1<=wi,hi<=1061<=w_{i},h_{i}<=10^{6} ).

输出格式

In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 00 in the single line.

输入输出样例

  • 输入#1

    2 1 1
    2 2
    2 2

    输出#1

    1
    1
  • 输入#2

    3 3 3
    5 4
    12 11
    9 8

    输出#2

    3
    1 3 2
首页