ONORIVER1 - Ono at the river 1

no tags 

Oňo the grasshopper wants to cross the river. But the river is very wide – w meters from one bank to the other, and Oňo can only jump up to d meters at once. Fortunately, there are n lily pads growing in the river. They’re not big enough yet, but once they are adult, they will be able to hold Oňo’s weight.

The i-th lily pad is located mi meters away from the left bank, where Oňo is right now. It will become able to support Oňo si seconds from now. But ei seconds from now it will become too old and die.

Oňo is very fast and he can perform multiple jumps (each up to d meters) in a single second – every jump is practically instant. But he is still nervous. If he doesn’t plan things through, he could end up jumping across some lily pads only to find out there is no way forward, and now the lily pads behind him are gone and he can’t even get back! Oh, the horror! To prevent this, Oňo will only jump across the lily pads when he can immediately get from one side of the river to the other without stopping.

It would be great if someone wrote a program telling him at what time he can do so, and the total time that the river is crossable.


Each lily pad has a time si when it turns adult and a time ei when it dies; it can hold Oňo from the si-th to the ei-th second. The lily pad is located mi meters from the left bank of the river.

Find the earliest time that Oňo can cross the river without stopping, and also how many seconds there are such that he is able to do so.

Note that Oňo is not brave enough to jump from a lily pad which grows old at time t to a lily pad which becomes adult at the same time t - in other words, you may imagine that at the beginning of each second, first the appropriate lily pads die and then the appropriate lily pads become adult.


The first line contains an integer 1 ≤ T ≤ 3 - the number of test cases. The only input file with T > 1 is the sample shown below.

T test cases follow, each ends with a blank line.

The first line contains three integers n, w and d - the number of lily pads, the width of the river, and Oňo’s jump distance, where 1 ≤ n ≤ 500 000 and 1 ≤ d < w ≤ 109.

n lines will follow, each containing three integers mi si ei describing one lily pad: its distance in meters from the left bank, the time it turns adult, and the time it grows old. 0 < mi < w and 1 ≤ si < ei ≤ 1015.

No two lily pads with the same position mi will be alive at the same time, in particular if any two lily pads have the same mi, one will die at least a second before the other becomes adult.


For each test case, output two integers e and t in a single line, where e is the earliest time at which Oňo can jump all the way from the left to the right bank of the river without stopping, and t is the total number of seconds during which he can do so (not necessarily continuously from e).

If Oňo can never cross the river, print e as −1.



7 60 10
10 1 10
20 1 7
20 8 11
40 1 20
50 4 15
30 5 12
30 1 3

2 100 80
1 1 5
81 5 123

20 5 1
1 1 189
2 1 2
3 1 2
4 1 2
2 109 189
3 109 189
4 109 323
1 281 462
2 281 323
3 281 323
2 337 743
3 337 462
4 337 462
1 616 743
3 616 743
4 616 1016
1 874 1327
2 874 1327
3 874 1327
4 1163 1327


5 4
-1 0
1 681

In the first case, at time 5, the first, second, fourth, fifth, and sixth lillies are alive, and Oňo can jump across. He can do so until the 7th second for a total of 2 seconds, when the second lily pad dies, then again from the 8th second to the 10th second, after which the first lily pad dies and the river becomes uncrossable forever.

In the second case the lily pads just barely miss themselves, and Oňo can never get across.

hide comments
ryloric: 2019-08-18 14:47:51

Hi @Hodobox, is my last submission(24260099) anywhere close to the time limit? I'm wondering if Ocaml is not the right language with this TL or if my solution is just too slow.

RE: I compiled it on my laptop, the sample runs fine, but the first input takes over half an hour (after which I killed it). I assume you have a slow algorithm.

@Hodobox: Thanks for taking the time!

Last edit: 2019-08-19 04:35:19

Added by:Hodobox
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem