1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include #include #include #include #include using namespace std; #define ll long long int abs(int x) {return x<0 ? -x : x;} int t,n,w,x,y,x2,y2; int s1[50001], X1[50001],X2[500001]; bool fc(int a, int b) {return X1[a]H[b];} }; multiset z; multiset::iterator it; int main(int argc, char** argv) { ios_base::sync_with_stdio(0); cin >> t; while (t--) { cin >> n >> w; for (int i=0;i> x >> y >> x2 >> y2; s1[i]=i+1; X1[i+1]=min(x,x2); H[i+1]=abs(y-y2); } for (int i=1;i<=n;i++) { cin >> x >> y >> x2 >> y2; X2[i]=min(x,x2); } sort(s1,s1+n,fc); //for (int i=0;ig) { block[*it]=s1[i]; z.erase(it); } z.insert(s1[i]); } while (!z.empty()) { it=z.begin(); block[*it]=-1; z.erase(it); } z.clear(); for (int i=n-1;i>=0;i--) { int g=w-H[s1[i]]; while (!z.empty() && H[*(it=z.begin())]>g) { blockleft[*it]=s1[i]; z.erase(it); } z.insert(s1[i]); } while (!z.empty()) { it=z.begin(); blockleft[*it]=-1; z.erase(it); } //for (int i=1;i<=n;i++) cout << i << ":" << block[i] << ' '; cout << '\n'; bool ok=true; for (int i=1;ok && i<=n;i++) { int b=block[i]; if (b>0) ok = X2[i]0) ok = ok && X2[b]