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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <list>

using namespace std;
using TaskList = list<int>;

#define MAX 1000010

void readData(const int n, int* p, int*k, int *c, TaskList* taskListStart, TaskList* taskListStop, int& minTime, int& maxTime)
{
	minTime = MAX;
	maxTime = 0;
	for (int i=0; i<n; ++i)
	{
		scanf("%d %d %d\n", &p[i], &k[i], &c[i]);
		taskListStart[p[i]].push_back(i);
		taskListStop[k[i]].push_back(i);
		minTime = min(minTime, p[i]);
		maxTime = max(maxTime, k[i]);
	}
}

void work(const int m, int*k, int *c, TaskList* taskListStart, TaskList* taskListStop, const int minTime, const int maxTime)
{
	vector<int> currentTasks;
	vector<int> toRemove;
	bool needSort = false;
	for (int i=minTime; i<=maxTime; ++i)
	{
		auto freePlace = [&i, &k, &c](int t){ return k[t] - i- c[t]; };
		auto cmp = [&k, &i, &c](int a, int b)
		{
			const int v1 = k[a] - i- c[a];
			const int v2 = k[b] - i- c[b];
			if (v1 == v2)
				return k[a] > k[b];
			else
				return v1 < v2;
		};
		for (int t: taskListStop[i])
		{
			auto it = find(currentTasks.begin(), currentTasks.end(), t);
			if (it!= currentTasks.end())
				currentTasks.erase(it);
		}
		for (int t: taskListStart[i])
		{
			currentTasks.push_back(t);
			needSort = true;
		}
		if (currentTasks.size() > m && needSort)
		{
			needSort = false;
			sort(currentTasks.begin(), currentTasks.end(), cmp);
		}
		if (currentTasks.size() > m)
		{
			needSort |= freePlace(currentTasks[m-1]) == freePlace(currentTasks[m]);
			needSort |= freePlace(currentTasks[m-1]) == freePlace(currentTasks[m]) - 1;
		}
		for (int i=0; i<min(m, (int)currentTasks.size()); ++i)
		{
			const int task = currentTasks[i];
			if (c[task] <= 1)
			{
				c[task]=0;
				toRemove.push_back(task);
			}
			else
				c[task]--;
		}
		needSort = true;
		for (int task: toRemove)
			currentTasks.erase(find(currentTasks.begin(), currentTasks.end(), task));
		toRemove.clear();
	}
}

int main()
{
	int n, m;
	scanf("%d %d\n", &n, &m);

	int *p = new int[n];
	int *k = new int[n];
	int *c = new int[n];

	TaskList* taskListStart = new TaskList[MAX];
	TaskList* taskListStop = new TaskList[MAX];

	int minTime, maxTime;
	readData(n, p, k, c, taskListStart, taskListStop, minTime, maxTime);
	work(m, k, c, taskListStart, taskListStop, minTime, maxTime);

	int sum = 0;
	for (int i=0; i<n; ++i)
		sum+=c[i];
	if (sum == 0)
		printf("TAK\n");
	else
		printf("NIE\n");
	return 0;
}