P9697 [GDCPC 2023] Canvas

There is a sequence of length $n$. At the beginning, all elements in the sequence equal to $0$. There are also $m$ operations, where the $i$-th operation will change the value of the $l_i$-th element in the sequence to $x_i$, and also change the value of the $r_i$-th element in the sequence to $y_i$. Each operation must be performed exactly once. Find the optimal order to perform the operations, so that after all operations, the sum of all elements in the sequence is maximized.

N/A

N/A

For the first sample test case, after performing operations $4, 1, 3, 2$ in order, the sequence becomes $\{2, 2, 2, 1\}$. The sum of all elements is $7$. For the second sample test case, after performing operations $2, 1$ in order, the sequence becomes $\{2, 0, 2, 1\}$. The sum of all elements is $5$.