Untitled diff
1 removal
75 lines
14 additions
88 lines
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
using namespace std;
#define SIZE 100000
#define SIZE 100000
#define MAX_VALUE 100002
#define MAX_VALUE 100002
int main () {
int main () {
int T, N, Q;
int T, N, Q;
cin >> T;
cin >> T;
while(T--) {
while(T--) {
cin >> N >> Q;
cin >> N >> Q;
int arr[SIZE];
int arr[SIZE];
for (int i = 0; i < N; ++i)
for (int i = 0; i < N; ++i)
{
{
scanf("%d", arr+i);
scanf("%d", arr+i);
}
}
for (int q = 0; q < Q; ++q)
for (int q = 0; q < Q; ++q)
{
{
int a, b, c, d;
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
scanf("%d %d %d %d", &a, &b, &c, &d);
a--; b--; c--; d--;
a--; b--; c--; d--;
if(a < c && c <=b) {
int t = b;
b = c-1;
c = t+1;
} else if( c < a && a <= d) {
int t = a;
a = d+1;
d = t-1;
}
if(a == c || (b-a < 0)) {
cout << "YES" << endl;
continue;
}
int countNums1[MAX_VALUE+2] = {0}; // 1-indexed, and an extra element as sentinal value
int countNums1[MAX_VALUE+2] = {0}; // 1-indexed, and an extra element as sentinal value
int countNums2[MAX_VALUE+2] = {0};
int countNums2[MAX_VALUE+2] = {0};
int minArr = MAX_VALUE, maxArr = 1;
int minArr = MAX_VALUE, maxArr = 1;
for (int i = a, j=c; i <= b; ++i, j++)
for (int i = a, j=c; i <= b; ++i, j++)
{
{
countNums1[arr[i]]++;
countNums1[arr[i]]++;
countNums2[arr[j]]++;
countNums2[arr[j]]++;
minArr = min(min(minArr, arr[i]), arr[j]);
minArr = min(min(minArr, arr[i]), arr[j]);
maxArr = max(max(maxArr, arr[i]), arr[j]);
maxArr = max(max(maxArr, arr[i]), arr[j]);
}
}
// cout << minArr << " " << maxArr << endl;
// cout << minArr << " " << maxArr << endl;
int i = minArr, j = minArr;
int i = minArr, j = minArr;
int misMatch = 0;
int misMatch = 0;
do {
do {
while(countNums1[i] == 0 && i <= maxArr) {
while(countNums1[i] == 0 && i <= maxArr) {
i++;
i++;
}
}
if(i > maxArr)
if(i > maxArr)
break;
break;
while(countNums2[j] == 0 && j <= maxArr) {
while(countNums2[j] == 0 && j <= maxArr) {
j++;
j++;
}
}
if(j > maxArr)
if(j > maxArr)
break;
break;
if(i != j) {
if(i != j) {
int minC = min(countNums1[i], countNums2[j]);
int minC = min(countNums1[i], countNums2[j]);
misMatch += minC;
misMatch += minC;
countNums1[i] -= minC;
countNums1[i] -= minC;
countNums2[j] -= minC;
countNums2[j] -= minC;
} else {
} else {
if(countNums1[i] < countNums2[j]) {
if(countNums1[i] < countNums2[j]) {
countNums2[j] -= countNums1[i];
countNums2[j] -= countNums1[i];
i++;
i++;
} else if(countNums2[j] < countNums1[i]) {
} else if(countNums2[j] < countNums1[i]) {
countNums1[i] -= countNums2[j];
countNums1[i] -= countNums2[j];
j++;
j++;
} else {
} else {
i++;
i++;
j++;
j++;
}
}
}
}
} while(misMatch < 2);
} while(misMatch < 2);
if(misMatch < 2)
if(misMatch < 2)
cout << "YES" << endl;
cout << "YES" << endl;
else
else
cout << "NO" << endl;
cout << "NO" << endl;
}
}
}
}
return 0;
return 0;
}
}