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 | #include <stdio.h>
#include <stdlib.h>
#define xint64 long long
#define MAXN 102400
int n;
int l[MAXN];
int a[MAXN];
int b[MAXN];
int ix[MAXN];
typedef struct {
int t;
xint64 v;
} t_pair;
int ip = 0;
t_pair pairs[2*MAXN];
int cmp(const void* a1, const void* a2) {
int i1 = *((const int*) a1);
int i2 = *((const int*) a2);
if (pairs[i1].t!=pairs[i2].t)
return pairs[i1].t-pairs[i2].t;
return pairs[i1].v-pairs[i2].v;
}
void norm(int l, int r) {
xint64 s = 0;
for (int i=l;i<=r;i++) {
s += pairs[ix[i]].v;
pairs[ix[i]].v = 0;
}
pairs[ix[r]].v = s;
}
void show() {
for (int i=0;i<ip;i++)
printf("%d %d\n", pairs[ix[i]].t, pairs[ix[i]].v);
printf("\n");
}
xint64 balance() {
xint64 s = 0;
for (int i=0;i<ip;i++)
s += ((xint64)pairs[ix[i]].t) * pairs[ix[i]].v;
return s;
}
int showE() {
xint64 eu = 0;
int lu = 0;
xint64 ed = 0;
int ld = 0;
for (int i=0;i<ip;i++) {
if (lu>=ld && ed+(lu-ld)*(((xint64)pairs[ix[i]].t))>eu)
return 0;
if (pairs[ix[i]].v<0) {
ed -= ((xint64)pairs[ix[i]].t) * pairs[ix[i]].v;
ld -= pairs[ix[i]].v;
} else {
eu += ((xint64)pairs[ix[i]].t) * pairs[ix[i]].v;
lu += pairs[ix[i]].v;
}
if (lu>=ld && ed+(lu-ld)*(1+((xint64)pairs[ix[i]].t))>eu)
return 0;
//printf("%d %d l:%d, e:%lld vs l:%d, e:%lld\n", pairs[ix[i]].t, pairs[ix[i]].v, lu, eu, ld, ed);
}
//printf("\n");
return 1;
}
void empty() {
int j = 0;
for (int i=0;i<ip;i++) {
if (pairs[ix[i]].v!=0) {
pairs[ix[j]].v = pairs[ix[i]].v;
pairs[ix[j]].t = pairs[ix[i]].t;
j++;
}
}
ip = j;
}
int main() {
int k;
scanf("%d", &k);
for (int i=0;i<k;i++) {
scanf("%d", &n);
for (int i=0;i<n;i++)
scanf("%d%d%d", &l[i], &a[i], &b[i]);
ip = 0;
for (int i=0;i<n;i++) {
ix[ip] = ip;
pairs[ip].t = a[i];
pairs[ip].v = -l[i];
ip++;
ix[ip] = ip;
pairs[ip].t = b[i];
pairs[ip].v = l[i];
ip++;
}
qsort(ix, ip, sizeof(int), cmp);
//show();
int lix = 0;
for (int i=0;i<ip;i++) {
if (pairs[ix[i]].t!=pairs[ix[lix]].t) {
norm(lix, i-1);
lix = i;
}
}
norm(lix, ip-1);
//show();
empty();
if (ip==0) {
printf("TAK\n");
continue ;
}
if (0!=balance() || pairs[ix[0]].v>0 || pairs[ix[ip-1]].v>0) {
printf("NIE\n");
continue ;
}
if (showE())
printf("TAK\n");
else
printf("NIE\n");
}
}
|