Canada Day Contest 2021 - Starfall

View as PDF

Submit solution


Points: 15
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

A meteor shower is approaching the Monkey Empire. At the t_ith second, a meteor will fall at (x_i,y_i) and destroy the planet. Luckily, the monkeys have a square tarp that they can use to catch the meteors. They can set up the tarp at any location initially at time 0, but once it has been set, the tarp can only be moved by up to K units in the \pm x and \pm y direction per second independently (You can move K units in both directions at once). In addition, the tarp is aligned with the x and y axis and cannot be rotated. What is the minimum tarp side length required to catch all meteors?

Assume the meteors have insignificant size.

Input Specification

The first line contains an integer n, the number of meteors, and K, the tarp speed.

The next n lines contain three integers each: t_i, x_i, and y_i, the time and location of the ith meteor strike. The input is given in order of nondecreasing time.

Output Specification

Output the minimum side length of the tarp.

Constraints

1 \le n \le 400\,000

0\le K \le 400\,000

0 \le t_i, x_i ,y_i \le 10^9

Sample Input 1

2 0
1 0 0
2 0 3

Sample Output 1

3

Explanation For Sample 1

The tarp has a speed of 0, so it cannot move. It must be big enough to cover both (0,0) and (0,3) at the same time.
diagram

Sample Input 2

2 1
1 0 0
2 3 3

Sample Output 2

2

Explanation For Sample 2

At time 1, the bottom left corner of the tarp is at (0,0). It moves 1 unit up and right by time 2. The top right corner now covers (3,3).

Sample Input 3

3 1
1 100 100
3 100 105
103 0 5

Sample Output 3

3

Explanation For Sample 3

The tarp starts with the bottom left corner at (100,100) to catch the first meteor, moves 2 units up to catch the second meteor, then moves 100 units left to catch the third meteor.

Sample Input 4

3 1000
1 0 0
1 5 1
2 100 100

Sample Output 4

5

Sample Input 5

3 100
0 1 3
1 4 2
5 0 0

Sample Output 5

0

Comments

There are no comments at the moment.