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
#include<iostream>
#include<algorithm>
using namespace std;

class Prost {
public:
    Prost() {}
    Prost(int wX, int wY, int dl, int wy, int nu) : wspX(wX), wspY(wY), dlug(dl), wys(wy), num(nu) {}
    int wspX, wspY, dlug, wys, num;
    friend bool operator <(const Prost & pr1, const Prost & pr2) {
        return pr1.wspX < pr2.wspX;
    }
};


const int ROZMIAR = 50100, TREE_SIZE = 1 << 16;
int nTest, ile, wys, wx1, wy1, wx2, wy2;
int drzewo[TREE_SIZE * 2];
int indWyn[ROZMIAR];
Prost tab[ROZMIAR], wyn[ROZMIAR];

void budujDrzewo() {
    for(int i = 0; i < ile; i++) {
        drzewo[i + TREE_SIZE] = tab[i].wys;
        drzewo[i] = 0;
    }
    for(int i = ile - 1; i >= 1; i--) {
        drzewo[i] = max(drzewo[i * 2], drzewo[i * 2 + 1]);
    }
}

int zwrocMaks(int odkad, int dokad) {
    odkad += TREE_SIZE;
    dokad += TREE_SIZE;
    int wynik = max(drzewo[odkad], drzewo[dokad]);
    while(odkad / 2 < dokad / 2) {
        if(odkad % 2 == 0) wynik = max(wynik, drzewo[odkad + 1]);
        if(dokad % 2 == 1) wynik = max(wynik, drzewo[dokad - 1]);
        odkad /= 2;
        dokad /= 2;
    }
    return wynik;
}

void wczytaj() {
    cin >> ile >> wys;
    for(int i = 0; i < ile; i++) {
        cin >> wx1 >> wy1 >> wx2 >> wy2;
        tab[i] = Prost(wx1, wy1, wx2 - wx1, wy2 - wy1, i);
    }
    sort(tab, tab + ile);
    budujDrzewo();
    for(int i = 0; i < ile; i++) {
        cin >> wx1 >> wy1 >> wx2 >> wy2;
        wyn[i] = Prost(wx1, wy1, wx2 - wx1, wy2 - wy1, i);
    }
    sort(wyn, wyn + ile);
    for(int i = 0; i < ile; i++) {
        indWyn[wyn[i].num] = i;
    }
}

bool rozw() {
    for(int i = 0; i < ile; i++) {
        Prost prost = wyn[indWyn[tab[i].num]];
        if(i >= indWyn[tab[i].num]) continue;
        if(tab[i].wys + zwrocMaks(i + 1, indWyn[tab[i].num]) > wys) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> nTest;
    for(int i = 0; i < nTest; i++) {
        wczytaj();
        if(rozw()) cout << "TAK" << endl;
        else cout << "NIE" << endl;
    }
    return 0;
}