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

int N,M,maxend=0,startp=0,endp=0;
std::vector<int> start,end,etime;
std::vector<int> starts, ends;
std::vector<int> active;
std::vector<int> reserve;
std::vector<int> run;

static inline bool activeCmp(int lhs, int rhs) {
	return reserve[lhs]<reserve[rhs];
}

int main() {
	scanf("%d %d",&N,&M);
	for (int i=0;i<N;++i) {
		int p,k,c;
		scanf("%d %d %d",&p,&k,&c);
		start.push_back(p);
		end.push_back(k);
		etime.push_back(c);
		starts.push_back(p);
		ends.push_back(k);
		reserve.push_back(0);
		run.push_back(0);
		maxend = std::max(maxend,k);
	}

	std::sort(starts.begin(), starts.end());
	std::sort(ends.begin(), ends.end());

	for (int t=0; t<=maxend; ++t) {
		//add to active
		bool search = false;
		while (startp<N && starts[startp]<=t) {
			search = true;
			startp++;
		}

		if (search) {
			for (int j=0; j<N; ++j) {
				if (start[j]==t) {
					active.push_back(j);
					reserve[j] = end[j]-start[j]-etime[j];
				}
			}
		}

		//delete from active
		search = false;
		while (endp<N && ends[endp]<=t) {
			search = true;
			endp++;
		}

		if (search) {
			for (int j=0; j<N; ++j) {
				if (end[j]==t) {
					active.erase(std::remove(active.begin(), active.end(), j), active.end());
				}
			}
		}

		//decrease
		if (M<active.size()) {
			std::nth_element(active.begin(), active.begin()+M-1, active.end(), activeCmp);
		}

		for (int j=0; j<active.size(); ++j) {
			if (j>=M) {
				reserve[active[j]]--;
				if (reserve[active[j]] < 0) {
					printf("NIE\n");
					return 0;
				}
			} else {
				if (++run[active[j]] == etime[active[j]]) reserve[active[j]]+=1000005;
			}
		}
	}

	printf("TAK\n");
	return 0;
}