以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Problem D. Almost Certainly
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 512 megabytes
Let’s say that two multisets are equal almost certainly if they are equal up to one element. That is,
it should be possible to change at most one element in the first multiset so that they become equal. For
example, the multisets {1, 1, 2} and {1, 2, 3} are equal almost certainly, {1, 1, 1} and {1, 1, 1} are equal
almost certainly, and {1, 2, 3} and {3, 4, 5} are not equal almost certainly.
A boy named Vasya really liked this definition and immediately came up with a problem about it.
Vasya has two arrays a and b, where ai ≥bi for all i from 1 to n. Vasya can apply the following operation
to array a as many times as he wants (possibly zero times): choose any index i (1 ≤i ≤n) and subtract
1 from ai. At the same time, Vasya does not change array b.
Vasya quickly understood what sequence of operations is needed to make the multiset of values of arrays
a and b equal almost certainly. Therefore, Vasya made the task more complicated — now for each prefix
of these arrays, he wants to know the minimum number of operations needed to make the prefixes of the
arrays equal almost certainly.
More formally, for each k from 1 to n, Vasya wants to take the elements a1, a2, . . . , ak, as well as the
elements b1, b2, . . . , bk. Vasya wants to know the minimum number of operations needed to make the
multisets of these elements equal almost certainly. Note that the task for each k is solved independently.
Input
Each test consists of one or more sets of input data. The first line contains a single integer t
(1 ≤t ≤100 000) — the number of sets of input data. Then follows the description of the sets of
input data.
The first line of each set of input data contains a single integer n (1 ≤n ≤200 000) — the size of arrays
a and b.
The second line of each set of input data contains n integers a1, a2, . . . , an (1 ≤ai ≤109) — the elements
of array a.
The third line of each set of input data contains n integers b1, b2, . . . , bn (1 ≤bi ≤ai) — the elements
of array b.
Let N be the sum of n for all sets of input data in one test. It is guaranteed that N ≤200 000.
Output
For each set of input data, output n integers, each of which is the answer to the task for each possible
prefix length. It can be shown that the answer always exists.
Page 10 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Examples
standard input standard output
4 0 1
2 0 0
3 4 0 4 2
1 2 0 10 30 48
2
3 4
1 3
3
11 17 14
1 13 10
4
100 11 50 42
30 1 20 5
3 0 1 1 3
4 0 1 3 6
2 4 5 12 0 2 3 3
1 3 4 10
4
3 5 8 20
1 2 6 7
4
4 4 4 4
1 2 3 4
Note
Consider the first set of input data in the first example.
• For a prefix of length 1, nothing needs to be done.
• For a prefix of length 2, a1 = 3 needs to be decreased by 1 once, after which a will be equal to [2, 4],
b will be equal to [1, 2], and they will be equal almost certainly.
Consider the third set of input data in the first example.
• For a prefix of length 1, nothing needs to be done.
• For a prefix of length 2, a2 = 17 needs to be decreased by 4 times, after which the prefix of a will
be equal to [11, 13], the prefix of b will be equal to [1, 13], and they will be equal almost certainly.
• For a prefix of length 3, a1 = 11 needs to be decreased by 1 and a3 = 14 needs to be decreased by
1, after which a will be equal to [10, 17, 13], b will be equal to [10, 13, 11], and they will be equal
almost certainly.
Scoring
The tests for this problem consist of six groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed. Please note that passing the example tests is not
required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.
Page 11 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Additional constraints
Group Points Required groups Comment
N
0 0 – – Examples.
1 16 N ⩽100 0 –
2 13 N ⩽500 0, 1 –
3 24 N ⩽3000 0 – 2 –
4 13 – – ai < bi+1
5 14 – 4 ai ⩽ai+1, bi ⩽bi+1
6 20 – 0 – 5 Offline-evaluation.
It can be shown that all tests of the fourth group satisfy the constraints of the fifth group.
Page 12 of 12