Public Judge

pjudge

Time Limit: 5 s Memory Limit: 512 MB Total points: 100

#21659. 【PR #6】区间数颜色

Statistics

给定数轴上的 $N$ 个区间 $[L_i,R_i)$,满足两两不同且长度单调不降,即对 $1\le i<j\le n$ 保证 $R_i-L_i\le R_j-L_j$,且 $L_i=L_j$ 和 $R_i=R_j$ 不同时成立。

初始时数轴是白色的,进行 $N$ 次操作,每次选择一个之前没有选择过的区间 $[L_i,R_i)$,将这个区间染成黑色,要求染完之后黑色部分的总长度尽量小,若相同则选择编号最小的。求每次操作选择的区间的编号。

输入格式

第一行,一个正整数 $N$。

之后 $N$ 行,每行两个非负整数 $L_i,R_i$。

输出格式

一行,$N$ 个正整数,第 $i$ 个正整数表示第 $i$ 次选择的区间的编号。

样例一

input

6
1 2
2 3
3 4
4 5
1 3
3 5

output

1 2 5 3 4 6

样例二

input

4
3 7
10 14
1 6
6 11

output

1 3 2 4

样例三

见下发文件中的 ex_color3.inex_color3.ans,该样例符合子任务 $2$ 的特殊限制。

样例四

见下发文件中的 ex_color4.inex_color4.ans,该样例符合子任务 $3$ 的特殊限制。

样例五

见下发文件中的 ex_color5.inex_color5.ans,该样例符合子任务 $4$ 的特殊限制。

样例六

见下发文件中的 ex_color6.inex_color6.ans,该样例符合子任务 $5$ 的特殊限制。

数据范围

对于所有数据,$0 \le N\le 2.5\cdot 10^5$,$0\le L_i<R_i\le 10^9$,对 $1\le i<j\le n$ 保证 $R_i-L_i\le R_j-L_j$,且 $L_i=L_j$ 和 $R_i=R_j$ 不同时成立。

  • 子任务 $1$($10$ 分):$N,R_i\le 100$;
  • 子任务 $2$($10$ 分):$N\le 10^4$;
  • 子任务 $3$($20$ 分):不存在 $1\le i,j\le n$ 使得 $L_i<L_j<R_j<R_i$;
  • 子任务 $4$($20$ 分):不存在 $1\le i,j\le n$ 使得 $L_i<L_j<R_i<R_j$;
  • 子任务 $5$($40$ 分):无特殊限制。

时间限制:$\texttt{5s}$

空间限制:$\texttt{512MB}$