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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#define offset 65536
using namespace std;

vector <int> TREE;
int cars,parking_height,xx1,xx2,yy1,yy2,cars_heights[offset],cars_place[offset],patch;
priority_queue <pair<int, int> > start;
priority_queue <pair<int, int> > target;

void read(){
for(int k=0;k<2*offset+5;k++)TREE[k]=0;
cin >> cars >> parking_height;
for(int j=0;j<cars;j++){
    cin >> xx1 >> yy1 >> xx2 >> yy2;
    cars_heights[j]=abs(yy2 - yy1);
    start.push(make_pair(-xx1,j));
}
            //for(int h=0;h<cars;h++)cout<< " h" << h << "=" << cars_heights[h];
            //cout<<"\n"<< "start_size=" << start.size() << "\n";
for(int j=0;j<cars;j++){
    cin >> xx1 >> yy1 >> xx2 >> yy2;
    target.push(make_pair(-xx1,j));
}
            //cout <<"\n"<< "target_size=" << target.size() << "\n";
int l=0;
while(target.size()!=0){
    cars_place[l]=target.top().second;
    l++;
    target.pop();
}
            //for(int h=0;h<cars;h++)cout<< " p" << h << "=" << cars_place[h];
            //cout <<"\n"<< "target_size=" << target.size() << "\n";
}

int supmax(int a,int b,int x,int y,int v){
if(a==x && b==y)return TREE[v];
int medium = (x+y)/2;
if(a>=medium)return supmax(a,b,medium,y,v*2+1);
else if(b<medium)return supmax(a,b,x,medium,v*2);
else return max(supmax(a,medium,x,medium,v*2), supmax(medium,b,medium,y,v*2+1));
}

void solve(){
while(start.size()!=0){
    //cout << cars_heights[start.top().second] << " " << supmax(cars_place[start.top().second]+offset,2*offset,offset,2*offset,1) << " ";
    if((cars_heights[start.top().second] + supmax(cars_place[start.top().second]+offset,2*offset,offset,2*offset,1)) > parking_height){
    cout << "NIE" << "\n";
    return;
    }
 patch = start.top().second + offset;
 TREE[patch]=cars_heights[start.top().second];
 while(patch!=0){
    patch/=2;
    TREE[patch]=max(TREE[patch*2],TREE[(patch*2)+1]);
 }
    start.pop();
}
cout << "TAK" << "\n";
}

int main(){
ios_base::sync_with_stdio(0);
int tests;
TREE.resize(2*offset+10);
cin >> tests;
for(int i=0;i<tests;i++){
read();
solve();
}}