Topics

Ninja and the experiment

Moderate
0/80
Average time to solve is 35m
Contributed by
0 upvote

Problem statement

Ninja performed an experiment 'N' times. In each attempt, he took 'M' readings and noted them down.

For any attempt to be successful, all the readings should be in non-decreasing order.

Due to some malfunctioning of the instrument, the readings were quite inaccurate.

For the evaluations of his work, Ninja has to answer 'Q' queries.

In each query, he is given two integers, 'L' and 'R', and he needs to return 'YES', if he has performed any of the experiments successfully, only considering the readings in the range 'L' to 'R'. Else return 'NO'.

Example:
Input: 'N' = 3, 'M'=3, 'Q' = 1, READINGS =[[1, 3, 2], [4, 2, 3], [1, 2, 3]]

For a query, L = 2 and R = 3 (1-based indexing)

Output: YES

If we only consider the readings in the range [L, R], the readings are [[3, 2], [2, 3], [2, 3]].
The experiment is successful on the second and the third attempt.
Hence we return 'YES'.
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
1 <= T <= 10
1 <= N*M <= 10^5
1 <= Q <= 10^5
1 <= L,R <= M

Sum of N*M Over all the Test cases <= 10^5 and sum of Q Over all the Test cases <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
4 5
1 3 4 5 4
2 1 5 5 4
3 3 2 3 3
5 2 3 2 4
3
1 1
2 5
4 5
1 1
1
1
1 1
Sample Output 1 :
YES
NO
YES
YES
Explanation Of Sample Input 1 :
For the first case:

'N' = 5, 'M' = 4, 'Q' = 3

Output:

YES
NO
YES

If we only consider the readings in the range [1, 1], the readings are [[1], [2], [3], [5]].
All the experiments are successful.
Hence we return 'YES'.
If we only consider the readings in the range [2, 5], the readings are [ [3 ,4 ,5 ,4],

[1 ,5 ,5 ,4], [3 ,2 ,3 ,3], [2 ,3 ,2 ,4] ]. All the experiments are unsuccessful. Hence we return 'NO'. If we only consider the readings in the range [4, 5], the readings are [[5, 4], [5, 4], [3, 3], [2, 4]]. The experiment is successful on the third and the fourth attempt. Hence we return 'YES'.

For the Second case:

'N' = 1, 'M' = 1, 'Q' = 1

Output:

YES

If we only consider the readings in the range [1, 1], the readings are [[1]].
The experiment is successful on the first attempt.
Hence we return 'YES'.
Sample Input 2 :
1
4 5
1 3 4 5 4
2 1 5 5 4
3 3 2 3 3
5 2 3 2 4
3
3 5
1 3
1 5
Sample Output 2 :
YES
YES
NO
Console