#B. Tea Queue

    远端评测题 1000ms 256MiB

Tea Queue

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Tea Queue

题面翻译

题面:

有n个学生排队喝茶。

第i 个学生在lil_i的时刻来排队。如果在同一时刻有多名学生来排队,那么id 较大的学生就会在id 较小的学生之后。

队列中的学生的行为如下:如果学生面前没有人排队,那么他就用茶一秒钟,然后出队。否则会等待。如果第i 个学生在rir_i的开始,仍然喝不到茶(队列前面有人),那么他就离开队伍了。

输入:

第一行:t,数据组数

每组数据的开头输入n,学生数

接下来n行每行为lil_i , rir_i

输出:

对于每组数据输出一行n个数,每个数表示这个学生喝到茶的时间,如果不能喝到就输出0

Translated by @@Lyrance

题目描述

Recently n n students from city S moved to city P to attend a programming camp.

They moved there by train. In the evening, all students in the train decided that they want to drink some tea. Of course, no two people can use the same teapot simultaneously, so the students had to form a queue to get their tea.

i i -th student comes to the end of the queue at the beginning of li l_{i} -th second. If there are multiple students coming to the queue in the same moment, then the student with greater index comes after the student with lesser index. Students in the queue behave as follows: if there is nobody in the queue before the student, then he uses the teapot for exactly one second and leaves the queue with his tea; otherwise the student waits for the people before him to get their tea. If at the beginning of ri r_{i} -th second student i i still cannot get his tea (there is someone before him in the queue), then he leaves the queue without getting any tea.

For each student determine the second he will use the teapot and get his tea (if he actually gets it).

输入格式

The first line contains one integer t t — the number of test cases to solve ( 1<=t<=1000 1<=t<=1000 ).

Then t t test cases follow. The first line of each test case contains one integer n n ( 1<=n<=1000 1<=n<=1000 ) — the number of students.

Then n n lines follow. Each line contains two integer li l_{i} , ri r_{i} ( 1<=li<=ri<=5000 1<=l_{i}<=r_{i}<=5000 ) — the second i i -th student comes to the end of the queue, and the second he leaves the queue if he still cannot get his tea.

It is guaranteed that for every condition li1<=li l_{i-1}<=l_{i} holds.

The sum of n n over all test cases doesn't exceed 1000 1000 .

Note that in hacks you have to set t=1 t=1 .

输出格式

For each test case print n n integers. i i -th of them must be equal to the second when i i -th student gets his tea, or 0 0 if he leaves without tea.

样例 #1

样例输入 #1

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

样例输出 #1

1 2 
1 0 2

提示

The example contains 2 2 tests:

  1. During 1 1 -st second, students 1 1 and 2 2 come to the queue, and student 1 1 gets his tea. Student 2 2 gets his tea during 2 2 -nd second.
  2. During 1 1 -st second, students 1 1 and 2 2 come to the queue, student 1 1 gets his tea, and student 2 2 leaves without tea. During 2 2 -nd second, student 3 3 comes and gets his tea.

4.19晚6点半练习及作业

未认领
状态
已结束
题目
2
开始时间
2024-4-19 18:15
截止时间
2024-4-27 23:59
可延期
24 小时