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

using namespace std;

using i64 = long long;
using i32 = int;

template<typename T> T load() { T x; cin >> x; return x; }
template<typename T> vector<T> loadN(int s) { vector<T> vt(s); for(auto& el : vt) el = load<T>(); return vt; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vt) { for(auto& el : vt) os << el << ' '; return os; }

template<typename F> void doTests(i32 t, F f) { while(t --> 0) cout << (f() ? "TAK\n" : "NIE\n"); }

struct Mug {
	bool isHeating() const { return bTemp <= eTemp; }
	i64 energyChange() const { return (eTemp - bTemp) * v; }
	friend istream& operator>>(istream& in, Mug& x) { return in >> x.v >> x.bTemp >> x.eTemp; }
	i64 v, bTemp, eTemp;
};

struct Event {
	bool isCollingStart() const { return type == 0; }
	bool isCoolignEnd() const { return type == 1; }
	bool isHeatingStart() const { return type == 2; }
	bool isHeatingEnd() const { return type == 3; }
	i64 v, temp, type;
};

i32 main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	doTests(load<i32>(), [&](){
		auto n = load<i32>();
		auto mugs = loadN<Mug>(n);
		auto events = vector<Event>();

		auto sum = i64{0};
		for(auto& mug : mugs) {
			events.push_back(Event{mug.v, mug.bTemp, 0 + 2 * mug.isHeating()});
			events.push_back(Event{mug.v, mug.eTemp, 1 + 2 * mug.isHeating()});
			sum += mug.energyChange();
		}

		if(sum != 0) return false;

		sort(events.begin(), events.end(), [](const Event& lhs, const Event& rhs){
			return lhs.temp < rhs.temp;
		});

		auto lastTemp = events[0].temp; // n >= 1
		
		i64 onLeft = 0;
		i64 coolingVolume = 0;
		i64 heatingVolume = 0;

		for(auto& event : events) {
			auto currTemp = event.temp;

			onLeft += (heatingVolume - coolingVolume) * (currTemp - lastTemp);
		 
			if(event.isCollingStart()) {
				coolingVolume -= event.v;
			} else if(event.isCoolignEnd()) {
				coolingVolume += event.v;
			} else if(event.isHeatingStart()) {
				heatingVolume += event.v;
			} else if(event.isHeatingEnd()) {
				heatingVolume -= event.v;
			}
			lastTemp = currTemp;
			
			if(onLeft < 0)
				return false;
		}

		return true;
	});
}