Question $2$

Max. score: $30\mathrm{.}00$

Complex subsequences

You have an array of infinite length with the value of all elements as zero. You are also given the following:

Two integers $N$ and $K$

In the next $N$ lines, you are given three integers $L,R,$ and $x.$ This means that you have to add $x$ to every element in the array from the index $L$ to $R($inclusive$)$

Your task is to find a subsequence from this array that meets the following conditions:

The subsequence should be of maximum length.

It should also be the smallest lexicographically.

The subsequence should form an increasing sequence of the form $Z,Z+K,Z+2*K,$dots,$Z+(L-1)*K$ for a value $Z$ and length $L.$

Notes

Remember that the sequence $A=[A_1,A_2,$dots,$A_L]$ is lexicographically smaller than the sequence $B=[B_1,B_2,$dots,$B_L]$ if the first element $($from the left$)$ in which thev differ is less in sequence A than in $B.$

$$

$$

$$

$$