Google OA 2024 - Complex Subsequence
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, ...., Z+(L-1)*K] for a value Z and length L.
Notes
- Remember that the sequence A = [A1, A2,.., AL] is lexicographically smaller than the sequence [B = [B1, B2,..., BL] if there exists an index i such that Aj Bj for all j < i and Ai < Bi
Output Format
Print the first integer that is the length of the subsequence and then the elements of the subsequence in the same line.
Constraints
1 <= N, K <= 2*10^5
1<=L<R <= 10^9
1< X <= 10^9
Sample Input
4 2
1 3 1
2 4 2
5 6 3
5 5 1
Sample Output
2 1 3