#PU1256. USACO 2022 December Contest, Silver — Problem 3. Range Reconstruction
USACO 2022 December Contest, Silver — Problem 3. Range Reconstruction
USACO 2022 December Contest, Silver — Problem 3. Range Reconstruction
题目描述
Bessie has an array , where and for all . She won't tell you itself, but she will tell you the range of each subarray of . That is, for each pair of indices , Bessie tells you . Given these values of , please construct an array that could have been Bessie's original array. The values in your array should be in the range .
输入格式
The first line contains . Another lines follow. The th of these lines contains the integers . It is guaranteed that there is some array with values in the range such that for all , .
输出格式
(见题面原文)
数据范围
Test 5 satisfies . Tests 6-8 satisfy for all . Tests 9-14 satisfy no additional constraints. Problem credits: Danny Mittal
样例
样例 1
3
0 2 2
0 1
0
1 3 2
For example, $r_{1, 3} = \max a[1\ldots 3] - \min a[1\ldots 3] = 3 - 1 = 2$.
样例 2
3
0 1 1
0 0
0
0 1 1
This example satisfies the constraints for subtask 1.
样例 3
4
0 1 2 2
0 1 1
0 1
0
1 2 3 2
This example satisfies the constraints for subtask 2.
样例 4
4
0 1 1 2
0 0 2
0 2
0
1 2 2 0