A13206. Movie Fan
编程题
普及/提高-
知识点
题目描述
The first line contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases in the input. The following are descriptions of the $t$ test cases.
The first line of each test case contains two integers $n$ and $m$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le m \le 10^9$ ) — the number of movies and the maximum number of movies that Polycarp can view per day.
In the next $n$ lines, the movies themselves are described, one per line, by a pair of integers $a_i$ , $b_i$ ( $1 \le a_i \le b_i \le 10^9$ ) — the first and last airing days for the $i$ -th movie.
It is guaranteed that the sum of the values $n$ for all test cases in the input does not exceed $2 \cdot 10^5$ .
The first line of each test case contains two integers $n$ and $m$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le m \le 10^9$ ) — the number of movies and the maximum number of movies that Polycarp can view per day.
In the next $n$ lines, the movies themselves are described, one per line, by a pair of integers $a_i$ , $b_i$ ( $1 \le a_i \le b_i \le 10^9$ ) — the first and last airing days for the $i$ -th movie.
It is guaranteed that the sum of the values $n$ for all test cases in the input does not exceed $2 \cdot 10^5$ .
输入格式
Print $t$ answers to given test cases in the order in which they appear in the input: the $i$ -th answer should consist of two lines. Print the integer $d$ in the first line of each test case answer:
- $d=0$ , if there is a schedule such that all movies are watched during airing,
- $d>0$ , if such a schedule does not exist — in this case, $d$ is equal to the minimum value of maximum among all the watching "delays" after the end of airing.
In the second line of the answer to each test case, print $n$ positive integers $t_1, t_2, \dots, t_n$ , where $t_i$ is the number of the day when Polycarp needs to watch the $i$ -th movie in the optimal schedule.
If there are several answers, print any of them.
- $d=0$ , if there is a schedule such that all movies are watched during airing,
- $d>0$ , if such a schedule does not exist — in this case, $d$ is equal to the minimum value of maximum among all the watching "delays" after the end of airing.
In the second line of the answer to each test case, print $n$ positive integers $t_1, t_2, \dots, t_n$ , where $t_i$ is the number of the day when Polycarp needs to watch the $i$ -th movie in the optimal schedule.
If there are several answers, print any of them.
输出格式
无
输入输出样例
输入 #1
3 7 2 1 2 1 3 2 2 2 3 1 1 2 3 1 2 5 3 1 1 1 1 1 1 1 1 1 1 6 1 13 13 31 31 25 25 12 12 14 14 10 10
输出 #1
1 1 3 2 3 1 4 2 1 1 1 1 2 2 0 13 31 25 12 14 10