LCC '21 Contest 4 S4 - Art Restoration

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Java 4.0s
Memory limit: 256M

Problem types

The battle has concluded! hewmatt10 has lost the brutal war and was once again, removed of all of his past artworks. Wanting to cherish the last moments of his reign before inevitably returning to [REDACTED]'s torture chamber, hewmatt10 wants to remember as many contents from his art gallery as possible.

Containing N paintings numbered from 1 to N each with a colourfulness c_i, hewmatt10 has recalled Q snapshots of him staring at his art gallery from afar, knowing the sum s_i of colourfulness across all paintings between l and r, inclusive.

Your task is to take these snapshots and determine a valid solution for the colourfulness of each painting.

Input Specification

On the first line, two integers, N and Q (1 \le N, Q \le 10^5).

On the next Q lines, three integers l, r (1 \le l \le r \le N), and s_i (1 \le \vert s_i \vert \le 10^9), representing an individual snapshot.

Output Specification

N integers c_i (0 \le  \vert  c_i \vert \le 10^{18}), indicating the colourfulness of each painting. If there are multiple solutions, output any one. It is guaranteed that there will be at least one solution.


For this problem, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask Description Points
1 1 \le N, Q \le 10. There will exist a solution such that  \vert c_i \vert \le 1. 10
2 1 \le N, Q \le 400. 15
3 1 \le N, Q \le 2000. 20
4 l will be unique for all queries. 15
5 No further constraints. 40

Sample Input

10 8
1 5 5
3 4 2
7 9 3
6 9 4
1 10 10
2 10 9
3 5 3
6 6 1

Sample Output

1 1 1 1 1 1 1 1 1 1


If you add up all of the subarrays in the snapshots, you will end up with s_i. For example, the sum of all elements from index 1 to 5 is 5, the sum of all elements from 3 to 4 is 2, etc. Note that 1 1 2 0 1 1 3 0 0 1 is also one of the various valid solutions.


There are no comments at the moment.