#include <cstdio> #include <climits> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define mp make_pair typedef vector<int> vi; inline int read() { int n; scanf("%d", &n); return n; } class MaxRT { vi t; int nn; int tmpmax(int i, int j, int a, int b, int id); public: MaxRT(int n); void set(int i, int v); int max(int i, int j); int get(int i); }; MaxRT::MaxRT(int n) { nn = n-1; nn |= (nn >> 1); nn |= (nn >> 2); nn |= (nn >> 4); nn |= (nn >> 8); nn |= (nn >> 16); nn++; t = vi(2*nn, 0); } void MaxRT::set(int i, int v) { i += nn; t[i] = v; for (i/=2; i>0; i/=2) t[i] = std::max(t[2*i], t[2*i+1]); } int MaxRT::max(int i, int j) { return tmpmax(i, j, 0, nn-1, 1); } int MaxRT::tmpmax(int i, int j, int a, int b, int id) { if (j < a || b < i) return 0; if (i < a) i = a; if (b < j) j = b; if (i == a && j == b) return t[id]; return std::max(tmpmax(i, j, a, (a+b)/2, 2*id), tmpmax(i, j, (a+b)/2+1, b, 2*id+1)); } int MaxRT::get(int i) { return t[i+nn]; } bool oneCase(int n) { int w = read(); vector<pii> a(n); for (int i=0; i<n; ++i) { int x1 = read(); read(); int x2 = read(); read(); int x3 = std::min(x1, x2); a[i] = mp(x3, i); } sort(a.begin(), a.end()); vi m(n); for (int i=0; i<n; ++i) m[a[i].second] = i; MaxRT rt(n); for (int i=0; i<n; ++i) { int x1 = read(); int y1 = read(); int x2 = read(); int y2 = read(); int x3 = std::min(x1, x2); a[i] = mp(x3, m[i]); rt.set(m[i], std::abs(y2 - y1)); } sort(a.begin(), a.end()); for (int i=0; i<n; ++i) { int id = a[i].second; if (id > 0 && rt.get(id) + rt.max(0, id - 1) > w) return false; rt.set(id, 0); } return true; } int main() { int t = read(); while (t--) printf("%s\n", oneCase(read()) ? "TAK" : "NIE"); return 0; }
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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #include <cstdio> #include <climits> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define mp make_pair typedef vector<int> vi; inline int read() { int n; scanf("%d", &n); return n; } class MaxRT { vi t; int nn; int tmpmax(int i, int j, int a, int b, int id); public: MaxRT(int n); void set(int i, int v); int max(int i, int j); int get(int i); }; MaxRT::MaxRT(int n) { nn = n-1; nn |= (nn >> 1); nn |= (nn >> 2); nn |= (nn >> 4); nn |= (nn >> 8); nn |= (nn >> 16); nn++; t = vi(2*nn, 0); } void MaxRT::set(int i, int v) { i += nn; t[i] = v; for (i/=2; i>0; i/=2) t[i] = std::max(t[2*i], t[2*i+1]); } int MaxRT::max(int i, int j) { return tmpmax(i, j, 0, nn-1, 1); } int MaxRT::tmpmax(int i, int j, int a, int b, int id) { if (j < a || b < i) return 0; if (i < a) i = a; if (b < j) j = b; if (i == a && j == b) return t[id]; return std::max(tmpmax(i, j, a, (a+b)/2, 2*id), tmpmax(i, j, (a+b)/2+1, b, 2*id+1)); } int MaxRT::get(int i) { return t[i+nn]; } bool oneCase(int n) { int w = read(); vector<pii> a(n); for (int i=0; i<n; ++i) { int x1 = read(); read(); int x2 = read(); read(); int x3 = std::min(x1, x2); a[i] = mp(x3, i); } sort(a.begin(), a.end()); vi m(n); for (int i=0; i<n; ++i) m[a[i].second] = i; MaxRT rt(n); for (int i=0; i<n; ++i) { int x1 = read(); int y1 = read(); int x2 = read(); int y2 = read(); int x3 = std::min(x1, x2); a[i] = mp(x3, m[i]); rt.set(m[i], std::abs(y2 - y1)); } sort(a.begin(), a.end()); for (int i=0; i<n; ++i) { int id = a[i].second; if (id > 0 && rt.get(id) + rt.max(0, id - 1) > w) return false; rt.set(id, 0); } return true; } int main() { int t = read(); while (t--) printf("%s\n", oneCase(read()) ? "TAK" : "NIE"); return 0; } |