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 )

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains two integers 'N' and 'M' denoting the number of attempts and the number of readings in each attempt.

The next 'N' lines of each test case contain 'M' space-separated integers, where the 'i'th line denotes the readings of the 'i'th attempt.
The next line contains the integer 'Q' denoting the number of queries asked.
The next 'Q' lines contain two integers 'L' and 'R' for each query.

Output format :

For each test case, You need to answer the 'Q' queries.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

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 :

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 :

Sample Output 2 :

YES
YES
NO

Console