CF377D.Developing Game

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Pavel is going to make a game of his dream. However, he knows that he can't make it on his own so he founded a development company and hired n workers of staff. Now he wants to pick n workers from the staff who will be directly responsible for developing a game.

Each worker has a certain skill level v__i. Besides, each worker doesn't want to work with the one whose skill is very different. In other words, the i-th worker won't work with those whose skill is less than l__i, and with those whose skill is more than r__i.

Pavel understands that the game of his dream isn't too hard to develop, so the worker with any skill will be equally useful. That's why he wants to pick a team of the maximum possible size. Help him pick such team.

帕维尔打算开发他梦想中的游戏。然而,他知道仅凭一己之力无法完成,因此成立了一家开发公司,并招聘了 nn 名员工。现在,他希望从这些员工中挑选出 nn 名直接负责游戏开发的人员。

每名员工都有一个特定的技能水平 viv_i。此外,每名员工都不愿与技能水平相差过大的人共事。换言之,第 ii 名员工拒绝与技能水平小于 lil_i 或大于 rir_i 的人合作。

帕维尔明白,他梦想中的游戏开发难度并不高,因此任何技能水平的员工都同样有用。正因如此,他希望组建一支规模尽可能大的团队。请你帮他选出这样的团队。

输入格式

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of workers Pavel hired.

Each of the following n lines contains three space-separated integers l__i, v__i, r__i (1 ≤ l__i ≤ v__i ≤ r__i ≤ 3·105) — the minimum skill value of the workers that the i-th worker can work with, the i-th worker's skill and the maximum skill value of the workers that the i-th worker can work with.

第一行包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5)—— Pavel 雇佣的工人数量。

接下来的 nn 行中,每行包含三个以空格分隔的整数 lil_i、viv_i、rir_i(1≤li≤vi≤ri≤3⋅1051 \leq l_i \leq v_i \leq r_i \leq 3 \cdot 10^5)—— 分别表示第 ii 个工人能够协作的工人的最低技能值、第 ii 个工人自身的技能值,以及第 ii 个工人能够协作的工人的最高技能值。

输出格式

In the first line print a single integer m — the number of workers Pavel must pick for developing the game.

In the next line print m space-separated integers — the numbers of the workers in any order.

If there are multiple optimal solutions, print any of them.

第一行输出一个整数 mm —— Pavel 为开发该游戏必须挑选的工人数量。

接下来一行输出 mm 个用空格分隔的整数 —— 工人的编号(顺序任意)。

若存在多个最优解,输出其中任意一个即可。

输入输出样例

  • 输入#1

    4
    2 8 9
    1 4 7
    3 6 8
    5 8 10

    输出#1

    3
    1 3 4
  • 输入#2

    6
    3 5 16
    1 6 11
    4 8 12
    7 9 16
    2 10 14
    8 13 15

    输出#2

    4
    1 2 3 5

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

首页