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
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int t, n, w, a, b, e;

int X1[50005];
int X2[50005];
int Y[50005];

int tab[50005];
int revtab[50005];
int perm[50005];
int revperm[50005];

int s;
int el[131105];
const int INF = 1000000001;

// MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka

	void Set(int p,int v) {
	for(p+=s, el[p]=v, p>>=1; p>0; p>>=1)
	    el[p] = max(el[p<<1], el[(p<<1)+1]);
    }
    
    int Find(int p, int k) {
	int m = -INF;
	p+=s; k+=s;
	while(p<k) {
	    if((p&1)==1) m=max(m,el[p++]);
	    if((k&1)==0) m=max(m,el[k--]);
	    p>>=1; k>>=1;
	}
	if(p==k) m=max(m,el[p]);
	return m;
    }

// MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka

bool compX1 (int F, int S)
{
	return (X1[F] < X1[S]);
}

bool compX2 (int F, int S)
{
	return (X2[F] < X2[S]);
}

bool program ()
{
	scanf("%d%d",&n,&w);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d%d%d%d",&X1[i],&a,&e,&b);
		if (e < X1[i]) X1[i] = e;
		Y[i] = max(b - a, a - b);
	}
	for (int i = 0; i < n; ++i)
	{
		scanf("%d%d%d%d",&X2[i],&a,&e,&b);
		if (e < X2[i]) X2[i] = e;
	}
	for (int i = 0; i < n; ++i) tab[i] = i;
	sort(tab, tab + n, compX1);
	for (int i = 0; i < n; ++i) revtab[tab[i]] = i;
	for (int i = 0; i < n; ++i) perm[i] = i;
	sort(perm, perm + n, compX2);
	for (int i = 0; i < n; ++i) perm[i] = revtab[perm[i]];
	for (int i = 0; i < n; ++i) revperm[perm[i]] = i;
	for (int i = 0; i < 131072; ++i) el[i] = 0;
	for (int i = 0; i < n; ++i) Set(i, Y[tab[perm[i]]]);
	for (int i = 0; i < n; ++i)
	{
		if (revperm[i] != 0)
		{
			e = Find(0, revperm[i] - 1);
			if (e + Y[tab[i]] > w)
			{
				printf("NIE\n");
				return 0;
			}
		}
		Set(revperm[i], 0);
	}
	printf("TAK\n");
	return 0;
}

int main ()
{
	s = 65536;
	scanf("%d",&t);
	while (t--) program();
	return 0;
}