Back To School '18: The Golden Porcupine

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 0.6s
Java 1.0s
Memory limit: 64M

Author:
Problem type

Ohani was tired of sitting in a mall, watching people hold hands. He hates public displays of affection (PDA). So, he decided to take a walk. He was walking through a magical forest when he came across a porcupine. He noticed that the porcupine's body was completely made of gold. The porcupine said:


Over a period of T seconds, I will shoot N quills out in total. The i^{th} quill exists only between the L_i^{th} and R_i^{th} seconds (inclusive).

The height of the i^{th} can be expressed as a_ix^2 + b_ix + c_i, where a_i, b_i, and c_i are constants for the i^{th} quill and x is the number of seconds the quill has been in the air. For the i^{th} quill, at time L_i, x = 0.

These quills have magical gravity and pass through anything, so it's perfectly fine for a_i to be more than 0 or the height of a quill to be less than 0 at any point in time.

Can you tell me the sum of the heights of all the quills at each second in time between 1 and T inclusive?


Ohani was able to solve the problem and get home just in time to play with legos with his brother. Ohani loves legos, and his brother is a lego lover too.

Input Specification

The first line will contain two integers, N, T (1 \le N \le 10^5, 1 \le T \le 10^5).

The next N lines will each contain five integers, L_i, R_i, a_i, b_i, c_i (1 \le L_i \le R_i \le T, 0 \le |a_i|, |b_i|, |c_i| \le 10^3).

Output Specification

Print T integers on one line, the t^{th} integer representing the sum of heights of quills at the t^{th} (1 \le t \le T) second in time.

Constraints

Subtask 1 [1%]

T = 1

Subtask 2 [4%]

N, T \le 1\,000

Subtask 3 [5%]

L_i = 1, R_i = T

Subtask 4 [20%]

a_i = 1, b_i = 1

Subtask 5 [70%]

No additional constraints.

Sample Input

2 6
1 6 1 3 2
3 4 2 2 -200

Sample Output

2 6 -188 -176 30 42

Explanation of Sample Output

The first quill's trajectory is shown as follows:

The second quill's trajectory is shown as follows:

At the 1^{st} second, the sum of the heights is only quill 1 at x=0 as quill 2 does not exist yet (2).

At the 2^{nd} second, the sum of the heights is only quill 1 at x=1 as quill 2 does not exist yet (6).

At the 3^{rd} second, the sum of the heights is quill 1 at x=2 and quill 2 at x=0 (12 + (-200) = -188).

At the 4^{th} second, the sum of the heights is quill 1 at x=3 and quill 2 at x=1 (20 + (-196) = -176).

At the 5^{th} second, the sum of the heights is only quill 1 at x=4 as quill 2 no longer exists (30).

At the 6^{th} second, the sum of the heights is only quill 1 at x=5 as quill 2 no longer exists (42).


Comments


  • 25
    aurpine  commented on Oct. 10, 2018, 5:56 a.m.

    nice problem