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 ith quill exists only between the Lith and Rith seconds (inclusive).

The height of the ith can be expressed as aix2+bix+ci, where ai, bi, and ci are constants for the ith quill and x is the number of seconds the quill has been in the air. For the ith quill, at time Li, x=0.

These quills have magical gravity and pass through anything, so it's perfectly fine for ai 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 (1N105,1T105).

The next N lines will each contain five integers, Li,Ri,ai,bi,ci (1LiRiT,0|ai|,|bi|,|ci|103).

Output Specification

Print T integers on one line, the tth integer representing the sum of heights of quills at the tth (1tT) second in time.

Constraints

Subtask 1 [1%]

T=1

Subtask 2 [4%]

N,T1000

Subtask 3 [5%]

Li=1,Ri=T

Subtask 4 [20%]

ai=1,bi=1

Subtask 5 [70%]

No additional constraints.

Sample Input

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

Sample Output

Copy
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 1st second, the sum of the heights is only quill 1 at x=0 as quill 2 does not exist yet (2).

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

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

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

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

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


Comments


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

    nice problem