#include<bits/stdc++.h> #define MAXN 65536 #define LL long long #define PB push_back using namespace std; struct car { LL d[4]; LL pos; }; bool cmp(car x, car y) { return x.d[0] < y.d[0]; } LL n, w, t; bool global_flag = false; vector<car> v, sec; car q; int wb[MAXN], tree[4*MAXN+2]; void add(int x, int val) { x += MAXN; tree[x] = max(tree[x], val); x /= 2; while(x != 1) { tree[x] = max(tree[x*2], tree[x*2+1]); x /= 2; } } void remove(int x) { x += MAXN; tree[x] = 0; x /= 2; while(x != 1) { tree[x] = max(tree[x*2], tree[x*2+1]); x /= 2; } } int query(int x, int y) { if(x > y)return 0; int res = 0; x += MAXN; y += MAXN; res = max(tree[y], tree[x]); while(x/2 != y/2) { if(!(x&1))res = max(res, tree[x+1]); if((y&1))res = max(res, tree[y-1]); x /= 2; y /= 2; } return res; } void solve() { v.clear(), sec.clear(); memset(wb, 0, sizeof(wb)); memset(tree, 0, sizeof(tree)); cin >> n >> w; for(LL i = 0; i < n; i++) { q.pos = i; for(LL j = 0; j < 4; j++) { cin >> q.d[j]; } if(q.d[3] < q.d[1])swap(q.d[3], q.d[1]); if(q.d[2] < q.d[0])swap(q.d[0], q.d[2]); v.PB(q); } for(LL i = 0; i < n; i++) { q.pos = i; for(LL j = 0; j < 4; j++) { cin >> q.d[j]; } if(q.d[3] < q.d[1])swap(q.d[3], q.d[1]); if(q.d[2] < q.d[0])swap(q.d[0], q.d[2]); sec.PB(q); } sort(v.begin(), v.end(), cmp); sort(sec.begin(), sec.end(), cmp); for(int i = 0; i < n; i++) { add(i, v[i].d[3]-v[i].d[1]); wb[v[i].pos] = i; } for(int i = 0; i < n; i++) { int x = sec[i].d[3]-sec[i].d[1]; if(x+query(0, wb[sec[i].pos]-1) > w) { // cout << x << ' ' << wb[sec[i].pos]-1 << endl; cout << "NIE\n"; return; } remove(wb[sec[i].pos]); } cout << "TAK\n"; } int main() { ios_base::sync_with_stdio(false); cin >> t; while(t--)solve(); }
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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | #include<bits/stdc++.h> #define MAXN 65536 #define LL long long #define PB push_back using namespace std; struct car { LL d[4]; LL pos; }; bool cmp(car x, car y) { return x.d[0] < y.d[0]; } LL n, w, t; bool global_flag = false; vector<car> v, sec; car q; int wb[MAXN], tree[4*MAXN+2]; void add(int x, int val) { x += MAXN; tree[x] = max(tree[x], val); x /= 2; while(x != 1) { tree[x] = max(tree[x*2], tree[x*2+1]); x /= 2; } } void remove(int x) { x += MAXN; tree[x] = 0; x /= 2; while(x != 1) { tree[x] = max(tree[x*2], tree[x*2+1]); x /= 2; } } int query(int x, int y) { if(x > y)return 0; int res = 0; x += MAXN; y += MAXN; res = max(tree[y], tree[x]); while(x/2 != y/2) { if(!(x&1))res = max(res, tree[x+1]); if((y&1))res = max(res, tree[y-1]); x /= 2; y /= 2; } return res; } void solve() { v.clear(), sec.clear(); memset(wb, 0, sizeof(wb)); memset(tree, 0, sizeof(tree)); cin >> n >> w; for(LL i = 0; i < n; i++) { q.pos = i; for(LL j = 0; j < 4; j++) { cin >> q.d[j]; } if(q.d[3] < q.d[1])swap(q.d[3], q.d[1]); if(q.d[2] < q.d[0])swap(q.d[0], q.d[2]); v.PB(q); } for(LL i = 0; i < n; i++) { q.pos = i; for(LL j = 0; j < 4; j++) { cin >> q.d[j]; } if(q.d[3] < q.d[1])swap(q.d[3], q.d[1]); if(q.d[2] < q.d[0])swap(q.d[0], q.d[2]); sec.PB(q); } sort(v.begin(), v.end(), cmp); sort(sec.begin(), sec.end(), cmp); for(int i = 0; i < n; i++) { add(i, v[i].d[3]-v[i].d[1]); wb[v[i].pos] = i; } for(int i = 0; i < n; i++) { int x = sec[i].d[3]-sec[i].d[1]; if(x+query(0, wb[sec[i].pos]-1) > w) { // cout << x << ' ' << wb[sec[i].pos]-1 << endl; cout << "NIE\n"; return; } remove(wb[sec[i].pos]); } cout << "TAK\n"; } int main() { ios_base::sync_with_stdio(false); cin >> t; while(t--)solve(); } |