LCC/Moose '20 Contest 3 S2 - Water Buckets

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

Larry is collecting buckets of water. He has N (1 \leq N \leq 2\cdot 10^5) buckets in a line, each starting empty and having a capacity of K (0 \leq K \leq 10^9). Every once in a while, someone comes to pour some water in a continuous segment of buckets, pouring the same amount of water in each bucket.

Larry wants to know when each bucket will overflow.

Input Specification

The first line of input will consist of three integers: N K and Q (1 \leq Q \leq 2\cdot 10^5), indicating that Q pours happpened.

The next Q lines of input will each consist of three integers, a, b (1 \leq a \leq b \leq N) and c (1 \leq c \leq 10^5), indicating someone poured c water into buckets in segment [a, b].

Output Specification

The output should consist of N space separated integers, the ith integer indicating that the ith bucket was filled after the a_ith pour (starting at 1).

If a bucket is never filled, output -1 instead.


Subtask 1 (10%)

N,Q \leq 10^3

Subtask 2 (90%)

No further constraints.

Sample Input

3 3 1
1 2 3

Sample Output

1 1 -1


There are no comments at the moment.