A15098. Restoring the Duration of Tasks
编程题
普及/提高-
知识点
题目描述
The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.
The descriptions of the input data sets follow.
The first line of each test case contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ).
The second line of each test case contains exactly $n$ integers $s_1 < s_2 < \dots < s_n$ ( $0 \le s_i \le 10^9$ ).
The third line of each test case contains exactly $n$ integers $f_1 < f_2 < \dots < f_n$ ( $s_i < f_i \le 10^9$ ).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The descriptions of the input data sets follow.
The first line of each test case contains one integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ).
The second line of each test case contains exactly $n$ integers $s_1 < s_2 < \dots < s_n$ ( $0 \le s_i \le 10^9$ ).
The third line of each test case contains exactly $n$ integers $f_1 < f_2 < \dots < f_n$ ( $s_i < f_i \le 10^9$ ).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
输入格式
For each of $t$ test cases print $n$ positive integers $d_1, d_2, \dots, d_n$ — the duration of each task.
输出格式
First test case:
The queue is empty at the beginning: $[ ]$ . And that's where the first task comes in. At time $2$ , Polycarp finishes doing the first task, so the duration of the first task is $2$ . The queue is empty so Polycarp is just waiting.
At time $3$ , the second task arrives. And at time $7$ , the third task arrives, and now the queue looks like this: $[7]$ .
At the time $10$ , Polycarp finishes doing the second task, as a result, the duration of the second task is $7$ .
And at time $10$ , Polycarp immediately starts doing the third task and finishes at time $11$ . As a result, the duration of the third task is $1$ .
An example of the first test case.
The queue is empty at the beginning: $[ ]$ . And that's where the first task comes in. At time $2$ , Polycarp finishes doing the first task, so the duration of the first task is $2$ . The queue is empty so Polycarp is just waiting.
At time $3$ , the second task arrives. And at time $7$ , the third task arrives, and now the queue looks like this: $[7]$ .
At the time $10$ , Polycarp finishes doing the second task, as a result, the duration of the second task is $7$ .
And at time $10$ , Polycarp immediately starts doing the third task and finishes at time $11$ . As a result, the duration of the third task is $1$ .
An example of the first test case.
输入输出样例
输入 #1
4 3 0 3 7 2 10 11 2 10 15 11 16 9 12 16 90 195 1456 1569 3001 5237 19275 13 199 200 260 9100 10000 10914 91066 5735533 1 0 1000000000
输出 #1
2 7 1 1 1 1 183 1 60 7644 900 914 80152 5644467 1000000000
说明/提示
First test case:
The queue is empty at the beginning: $[ ]$ . And that's where the first task comes in. At time $2$ , Polycarp finishes doing the first task, so the duration of the first task is $2$ . The queue is empty so Polycarp is just waiting.
At time $3$ , the second task arrives. And at time $7$ , the third task arrives, and now the queue looks like this: $[7]$ .
At the time $10$ , Polycarp finishes doing the second task, as a result, the duration of the second task is $7$ .
And at time $10$ , Polycarp immediately starts doing the third task and finishes at time $11$ . As a result, the duration of the third task is $1$ .
An example of the first test case.
The queue is empty at the beginning: $[ ]$ . And that's where the first task comes in. At time $2$ , Polycarp finishes doing the first task, so the duration of the first task is $2$ . The queue is empty so Polycarp is just waiting.
At time $3$ , the second task arrives. And at time $7$ , the third task arrives, and now the queue looks like this: $[7]$ .
At the time $10$ , Polycarp finishes doing the second task, as a result, the duration of the second task is $7$ .
And at time $10$ , Polycarp immediately starts doing the third task and finishes at time $11$ . As a result, the duration of the third task is $1$ .
An example of the first test case.