Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
//test sprawdzaj�cy szybko�� find-union z biblioteczki earla
//Krzysztof Kleiner
#include<cstdio>
#include<algorithm>
#define FOR(i, b, n) for ( int (i) = b; (i) < (n); (i)++)
#define FORR(i, b, n) for ( (i) = b; (i) < (n); (i)++)
#define REP(i, n) for ( int (i) = 0; (i) < (n); (i)++)
#define SC(n) scanf("%d", &(n))
#define SC2(n, m) scanf("%d%d", &(n), &(m))
#define SCLL(n) scanf("%lld", &(n))
#define PRT(n) printf("%d ", (n))
#define PRTLL(n) printf("%lld ", (n))
#define NXL printf("\n")
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;

const int MAXN=50020;

int w;
struct car {
    int w, xstart, xstop, ind;
};
car a[MAXN], temp[MAXN];
int suf[MAXN], sufind[MAXN];

bool mergesort (int p, int q)
{
    if(p==q) return 1;
    int s = (p+q)/2;
    if(! mergesort(p, s) ) return 0;
    if(! mergesort(s+1, q) ) return 0;;

    suf[s] = a[s].w;
    sufind[s] = a[s].ind;
    for (int i = s-1; i>=p; i--)
    {
        if(suf[i+1] > a[i].w) sufind[i] = sufind[i+1];
        else sufind[i] = a[i].ind;
        suf[i] = max(suf[i+1], a[i].w);
    }
    for (int i=p, j=s+1, b = p; i<=s || j<=q; )
    {
          if(j>q || (i<=s && a[i].xstop <= a[j].xstop))
                  temp[b++] = a[i++];
          else if(i > s)
          {
              temp[b++] = a[j++];

          }
          else
          {
              if(a[j].w + suf[i] > w)
              {
              //  printf("%d: %d %d %d %d %d bo %d\n", a[j].ind, a[j].w, a[j].xstart, a[j].xstop, suf[i], w, sufind[i]);
                return 0;
              }
              temp[b++] = a[j++];
          }
    }

      for (int i=p; i<=q; i++)
              a[i] = temp[i];
      return 1;
}

int main()
{
int z;
SC(z);
while(z--)
{
    int n;
    SC2(n, w);
    REP(i, n)
    {
        int x1, y1, x2, y2;
        SC2(x1, y1);
        SC2(x2, y2);
        a[i].w = abs(y1 - y2);
        a[i].xstart = min(x1, x2);
        a[i].ind = i;
    }

    REP(i, n)
    {
        int x1, y1, x2, y2;
        SC2(x1, y1);
        SC2(x2, y2);
        a[i].xstop = min(x1, x2);
    }

    sort(a, a+n, [](car c, car d) {
         return c.xstart < d.xstart;
         });
    if(mergesort(0, n-1)) printf("TAK\n");
    else printf("NIE\n");
}
return 0;
}