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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct car
{
   int left, right, height, id;
   car(int id, int x1, int y1, int x2, int y2)
      : left(x1), right(x2), height(y2 - y1), id(id)
   {}

};

typedef vector<int> vi;
typedef vector<int>::iterator vi_it;

typedef vector<car> vc;
typedef vector<car>::iterator vc_it;
typedef vector<car>::reverse_iterator vc_rit;

bool cars_cmp(const car & c1, const car & c2)
{
   return c1.right <= c2.right;
}

struct comparer
{
   static vector<int> order;
   comparer(const vector<car> & cars)
   {
      if (cars.size() > order.size())
         order.resize(cars.size());
      
      for (vector<car>::const_iterator c = cars.begin(); c != cars.end(); ++c)
         order[c->id] = c - cars.begin(); 
   }

   bool less(const car & c1, const car & c2) const
   {
      return order[c1.id] < order[c2.id];
   }
};

vector<int> comparer::order;

bool merge(vc_it l, vc_it r, vc_it m, int h, const comparer & cmp)
{
   static vector<car> merge_pom;
   static vector<int> max_h;
   merge_pom.clear();
   max_h.clear();
   merge_pom.insert(merge_pom.begin(), l, m);
   int akt_max = 0;
   for(vc_rit i = merge_pom.rbegin(); i != merge_pom.rend(); ++i)
   {
      akt_max = max(akt_max, i->height);
      max_h.push_back(akt_max);
   }

   vc_it i = merge_pom.begin(), j = m, k = l;
   vi_it ih = max_h.begin();
   bool ok = true;

   while(ok && i != merge_pom.end() && j != r)
   {
      if (cmp.less(*i, *j))
      {
         *k = *i;
         ++i;
         ++ih;
         ++k;
      }
      else
      {
         ok = (h - *ih) >= j->height;
         *k = *j;
         ++j;
         ++k;
      }
   }

   if (ok)
      while(i != merge_pom.end())
      {
         *k = *i;
         ++i;
         ++k;
      }

   return ok;
}

bool merge_sort_verify(vc_it l, vc_it r, int h, const comparer & cmp)
{
   if (distance(l, r) == 1) return true;
   vc_it m = l + distance(l, r) / 2;
   bool ok =   merge_sort_verify(l, m, h, cmp) &&
               merge_sort_verify(m, r, h, cmp);
   return ok && merge(l, r, m, h, cmp);
}


int main(int argc, char const *argv[])
{
   ios_base::sync_with_stdio(false);
   int t, n, w;
   cin >> t;
   vector<car> initial;
   vector<car> final;
   for (int i = 0; i < t; ++i)
   {
      cin >> n >> w;
      initial.clear();
      final.clear();
 
      int x1, y1, x2, y2;
      for (int j = 0; j < n; ++j)
      {
         cin >> x1 >> y1 >> x2 >> y2;
         initial.push_back(car(j, x1, y1, x2, y2));
      }
      for (int j = 0; j < n; ++j)
      {
         cin >> x1 >> y1 >> x2 >> y2;
         final.push_back(car(j, x1, y1, x2, y2));
      }

      sort(initial.begin(), initial.end(), cars_cmp);
      sort(final.begin(), final.end(), cars_cmp);

      comparer cmp(final);

      bool ok = merge_sort_verify(initial.begin(), initial.end(), w, cmp);
      if (ok)
         cout << "TAK" << endl;
      else
         cout << "NIE" << endl;

   }
   return 0;
}