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
#include <bits/stdc++.h>

using namespace std;

int main() {
	std::ios_base::sync_with_stdio(false);

	long long reps;
	cin >> reps;
	for (long long rep = 0; rep < reps; rep++) {
		long long items;
		cin >> items;
		map<long long, long long> supply;
		long long sz;
		long long ini;
		long long tar;
		long long last_elem = -1;
		for (long long item = 0; item < items; item++) {
			cin >> sz;
			cin >> ini;
			cin >> tar;
			if (ini > tar) {
				if (ini > last_elem) {
					last_elem = ini;
				}
				if (supply.find(tar) != supply.end()) {
					supply[tar] += sz;
				} else {
					supply.insert(make_pair(tar, sz));
				}
				if (supply.find(ini) != supply.end()) {
					supply[ini] -= sz;
				} else {
					supply.insert(make_pair(ini, -sz));
				}
			} else if (ini < tar) {
				if (tar > last_elem) {
					last_elem = tar;
				}
				if (supply.find(tar) != supply.end()) {
					supply[tar] += sz;
				} else {
					supply.insert(make_pair(tar, sz));
				}
				if (supply.find(ini) != supply.end()) {
					supply[ini] -= sz;
				} else {
					supply.insert(make_pair(ini, -sz));
				}
			}
		}
		map<long long, long long> cumulative;
		long long cum = 0;
		for (auto it = supply.begin(); it != supply.end(); it++) {
			cumulative.insert(make_pair(it -> first, cum));
			cum += it -> second;
		}
		long long oversupply = 0;
		long long last_supply = 0;
		long long cur_supply = 0;
		bool flag = true;
		for (auto it = cumulative.rbegin(); it != cumulative.rend(); it++) {
//			cout << "debug of long longerval: " << it -> first << " " << it -> second << endl;
//			cout << "past oversupply: " << oversupply << endl;
			last_supply = cur_supply;
			long long cur_elem = it -> first;
			cur_supply = it -> second;
			long long used = (last_elem - cur_elem) * last_supply;
			last_elem = cur_elem;
//			cout << "in span up to current: " << used << endl;
			oversupply += used;
//			cout << "cumulative oversupply: " << oversupply << endl;
			if (oversupply < 0) {
				flag = false;
			}
		}
		if (oversupply > 0) {
			flag = false;
		}
		if (flag) {
			cout << "TAK" << endl;
		} else {
			cout << "NIE" << endl;
		}
	}
	return 0;
}