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
#include <algorithm>
#include <cstdio>
#include <tuple>
//#include <iterator>

using namespace std;

typedef tuple<unsigned, unsigned> samochod; //x, h, nr
typedef tuple<unsigned, unsigned, unsigned, unsigned> wspolrzedne;

bool sprawdz(vector<samochod>, const vector<unsigned>, const unsigned);

int main() {
  unsigned t;
  scanf("%u", &t);
  for(unsigned i = 0; i < t; ++i) {
    unsigned n,w;
    scanf("%u%u", &n, &w);
    vector<wspolrzedne> pobrane(n);
    for(auto& x : pobrane)
     scanf("%u%u%u%u", &get<0>(x), &get<1>(x), &get<2>(x), &get<3>(x));
    vector<samochod> poczatkowa; poczatkowa.reserve(n);
    transform(begin(pobrane), end(pobrane), back_inserter(poczatkowa),
              [](wspolrzedne x) {return make_tuple(min(get<0>(x),get<2>(x)),
                                                   max(get<1>(x), get<3>(x)) - min(get<1>(x),get<3>(x)));});
    for(auto& x : pobrane)
     scanf("%u%u%u%u", &get<0>(x), &get<1>(x), &get<2>(x), &get<3>(x));
    vector<unsigned> koncowa; koncowa.reserve(n);
    transform(begin(pobrane), end(pobrane), back_inserter(koncowa),
              [](wspolrzedne x) {return min(get<0>(x), get<2>(x));});
    pobrane.clear(); pobrane.shrink_to_fit();
    const bool poprawnie = sprawdz(move(poczatkowa), move(koncowa), w);
      printf("%s\n", poprawnie ? "TAK" : "NIE");
   }
 }

class drzewo_przedzialowe {
  vector<unsigned> wierzcholki;
  inline unsigned ojciec(unsigned x) {
    return x / 2;
   }
  inline unsigned lewy_syn(unsigned x) {
    return 2 * x;
   }
  inline unsigned prawy_syn(unsigned x) {
    return 2 * x + 1;
   }
  public:
  template<typename T>
  drzewo_przedzialowe(const T p, const T q) {
    const unsigned n = distance(p,q);
    unsigned dl = 1;
    while(dl < n)
     dl <<= 1;
    wierzcholki.resize(dl * 2, 0);
   for_each(p, q, [&](decltype(*p) x){wierzcholki[dl+get<0>(x)] = get<1>(x);});
    for(unsigned i = dl-1; i > 0; --i) {
      wierzcholki[i] = max(wierzcholki[lewy_syn(i)], wierzcholki[prawy_syn(i)]);
     }
   }
  void update(unsigned i) {
    i += wierzcholki.size()/2;
    wierzcholki[i] = 0;
    i = ojciec(i);
    while(i != 0) {
      wierzcholki[i] = max(wierzcholki[lewy_syn(i)], wierzcholki[prawy_syn(i)]);
      i = ojciec(i);
     }
   }
  unsigned query(unsigned i, unsigned j) {
    if(j == 0)
     return 0;
    unsigned va = wierzcholki.size()/2 + i, vb = va-i+j - 1;
    unsigned wynik = max(wierzcholki[va], wierzcholki[vb]);
    while(ojciec(va) != ojciec(vb)) {
      if(va % 2 == 0)
       wynik = max(wynik, wierzcholki[va + 1]);
      if(vb % 2 == 1)
       wynik = max(wynik, wierzcholki[vb - 1]);
      va = ojciec(va);
      vb = ojciec(vb);
     }
    return wynik;
   }
 };

bool sprawdz(vector<samochod> samochody_poczatek, const vector<unsigned> samochody_koniec, const unsigned w) {
  vector<unsigned> poczatkowa; poczatkowa.reserve(samochody_poczatek.size());//kolejnosc
  unsigned iij = 0U;
  generate_n(back_inserter(poczatkowa), samochody_poczatek.size(),
             [&](void){return iij++;});
  vector<unsigned> koncowa(poczatkowa);
  sort(begin(poczatkowa), end(poczatkowa), [&](unsigned i, unsigned j){return get<0>(samochody_poczatek[i]) < get<0>(samochody_poczatek[j]);});
//return true;
  sort(begin(koncowa), end(koncowa), [&](unsigned i, unsigned j){return samochody_koniec[i] < samochody_koniec[j];});
  for(unsigned i = 0U; i < samochody_poczatek.size(); ++i)
   get<0>(samochody_poczatek[poczatkowa[i]]) = i;
//return true;
  drzewo_przedzialowe najwiekszy(begin(samochody_poczatek), end(samochody_poczatek));
  for(auto rozpatrywany : koncowa) {
    unsigned h_max = najwiekszy.query(0U, get<0>(samochody_poczatek[rozpatrywany]));
    if(h_max > w - get<1>(samochody_poczatek[rozpatrywany]))
     return false;
    najwiekszy.update(get<0>(samochody_poczatek[rozpatrywany]));
   }
  return true;
 }