DMOPC '22 Contest 1 P6 - Linear Swap

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

You are given an array of integers. There is a list of operations that you must apply to the array in some order. The -th operation has parameters , , and , and it can be applied by calling the following function:

bool apply(int a, int b, int s) {
int C = a;
for (int i = s; i <= N; i++) {
if (C > A[i]) swap(C,A[i]);
}
return C <= b;
}


The operation is successfully applied if and only if the function returns true. Your task is to determine whether there is some ordering of the operations such that all of the operations can be applied successfully. To ensure the integrity of your solution, there may be up to test cases.

Constraints

The sum of over all test cases does not exceed .

The sum of over all test cases does not exceed .

The sum of over all test cases does not exceed .

The sum of over all test cases does not exceed .

The sum of over all test cases does not exceed .

The sum of over all test cases does not exceed .

Input Specification

The first line contains an integer , the number of test cases. The remaining lines describe the test cases.

The first line of each test case contains integers and .

The second line of each test case contains integers .

The remaining lines of each test case each contain integers , , and , describing the operations of the test case.

Output Specification

For each test case, output one line containing YES if there is an ordering of the operations such that all of the operations can be applied successfully, or NO otherwise.

Sample Input

1
5 3
3 1 4 1 5
2 3 5
6 1 1
3 2 3

Sample Output

YES

Explanation for Sample

One possible solution is as follows:

1. Apply the third operation. This transforms into . Since at the end of the process and , this operation was applied successfully.
2. Apply the first operation. This transforms into . Since at the end of the process and , this operation was applied successfully.
3. Apply the second operation. This transforms into . Since at the end of the process and , this operation was applied successfully.