New Year's '19 P5 - Best Hat in Town

View as PDF

Submit solution

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

Problem types

The Mad Hatter's New Year's resolution is to find and obtain the best hat in town. He has already marked N stores which he wants to visit. However, he is broke, so he has decided to steal the hats instead. When the Mad Hatter steals from store i, he first enters the store. Next, he will throw away all but one hat, his favourite one so far, and take the store's h_i hats. He then wears these h_i+1 hats as he travels to his next destination. The Mad Hatter wants to steal from all n stores exactly once each in any order.

Due to the pretentious views of the hat-loving community, store i will only allow a person to enter if they are wearing at least a_i hats and at most b_i hats. Additionally, the Mad Hatter insists that he must steal if he visits a store. However, there is a way the Mad Hatter can break the two previous rules. A feline friend of his has lent him an invisibility charm. Whenever the Mad Hatter has it, he is invisible. This means he can sneak into any store, any number of times. He can also exit a store without stealing if he currently has it. The Mad Hatter will not steal when he has the charm. (He wants to see how the hats look on him before taking them!) For the Mad Hatter to stop using the charm, he must leave it at a store (enters invisibly, exits visibly). To start using it again, he must return to the store and exit with the charm (enters visibly, exits invisibly). He must also finish with the charm in his possession.

If the Mad Hatter starts with exactly one hat, can he complete his adventure successfully?

Clarification: The Mad Hatter may only change the number of his hats within stores (and based on the given rules).


1 \le N \le 200\,000
0 \le h_i \le N-1
1 \le a_i \le b_i \le N

Input Specification

The first line contains a single integer, N.
The next N lines each contain three space-separated integers, h_i, a_i, b_i.

Output Specification

Output yes if the Mad Hatter can steal from all the stores and end with the charm and no otherwise.

Sample Input 1

0 1 2
3 5 5
4 4 4
3 4 4
3 4 4

Sample Output 1


Explanation for Sample 1

The Mad Hatter can sneak into store 2 using the charm and leave it. Then, he steals the hats and leaves with 4. He can then enter the third store, where he steals and leaves with 5 hats. This allows him to return to store 2 to retrieve the charm and leave without stealing. Next, he enters the first store using the charm and leaves it there. Thus, he must steal and leave with one hat. He can then retrieve the charm again. After that, he can leave his charm in the fourth store and steal from it. Then, he may steal from the fifth store and return to the fourth store to retrieve the charm once again. Thus the Mad Hatter is done with the charm.

Sample Input 2

2 1 1
2 1 1
2 1 1

Sample Output 2


Explanation for Sample 2

Even though the Mad Hatter can enter any of the stores legally, he must enter with his charm and leave it there if he wants to steal. He leaves with 3 hats, regardless of the store. After that, he is no longer able to retrieve the charm, no matter what he does next. So the answer is no as he must end with the charm.


There are no comments at the moment.