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
130
131
132
133
134
135
136
137
138
139
140
141
//============================================================================
// Name        : potyczki2016.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <algorithm>    // std::reverse
#include <numeric>    // std::accumulate
using namespace std;

struct Event{
	int id;
	int action;
	int time;
	Event(int id, int action, int time){
		this->id = id;
		this->action = action;
		this->time = time;
	}
};
struct Interval{
	int id;
	int begin;
	int end;
	int cost;
	Interval(int id, int begin, int end, int cost){
		this->id = id;
		this->begin = begin;
		this->end = end;
		this->cost = cost;
	}
};

bool compareByTime(const Event &a, const Event &b)
{
    return a.time < b.time;
}

void get_soonest(int m, vector<int> & open_intervals, vector<int> & soonest_closing_intervals){
	for(int i=0; i<min(m, int(open_intervals.size())); i++)
		soonest_closing_intervals.push_back(open_intervals[i]);
}

void get_min_cost(vector<int> & soonest_closing_intervals, vector<Interval> & intervals, int & mincost){
	mincost = pow(10, 7);
	for(int i=0; i<soonest_closing_intervals.size(); i++){
		mincost = min(mincost, intervals[soonest_closing_intervals[i]].cost);
	}
}

vector<Event> events;
vector<Interval> intervals;

bool compare_ends (int i,int j) {
	return (intervals[i].end < intervals[j].end);
}

int main() {
	int n, m, pi, ki, ci;
	cin >> n >> m;

	int id = 0;
	for(int taskid=0; taskid<n; taskid++) {
		cin >> pi >> ki >> ci;
		events.push_back(Event(id, 0, pi));
		events.push_back(Event(id, 1, ki));
		id++;
		intervals.push_back(Interval(id, pi, ki, ci));
	}
	std::sort(events.begin(), events.end(), compareByTime);
	vector<int> open_intervals;

	//cout << "A" << endl;
	//processing
	int currtime = 0;
	int curridx = 0;
	while(curridx < events.size()){
		//cout << "open_intervals=";
		//for(int i=0; i<open_intervals.size(); i++)
			//cout << open_intervals[i] << " ";
		//cout << endl;

		vector<int> soonest_closing_intervals;
		get_soonest(m, open_intervals, soonest_closing_intervals);
		//cout << "soonest_closing_intervals=";
		//for(int i=0; i<soonest_closing_intervals.size(); i++)
			//cout << soonest_closing_intervals[i] << " ";
		//cout << endl;

		int mincost;
		get_min_cost(soonest_closing_intervals, intervals, mincost);
		//cout << "mincost=" << mincost << endl;
		//cout << "events[curridx].time=" << events[curridx].time << "currtime=" << currtime << endl;
		int bias = min(mincost, events[curridx].time-currtime);
		//cout << "bias=" << bias << endl;

		//update the tracked info the existing intervals:
		for (int intervalid=0; intervalid<soonest_closing_intervals.size(); intervalid++){
			intervals[soonest_closing_intervals[intervalid]].cost -= bias;
			if(intervals[soonest_closing_intervals[intervalid]].cost == 0){

				//cout << "before closing open_intervals soonest_closing_intervals[intervalid]=" << soonest_closing_intervals[intervalid] << endl;
				//for(int i=0; i<open_intervals.size(); i++)
					//cout << open_intervals[i] << " ";
				//cout << endl;
				std::remove(open_intervals.begin(), open_intervals.end(), soonest_closing_intervals[intervalid]);
				open_intervals.pop_back();
				//cout << "after closing open_intervals soonest_closing_intervals[intervalid]=" << soonest_closing_intervals[intervalid] << endl;
				//for(int i=0; i<open_intervals.size(); i++)
					//cout << open_intervals[i] << " ";
				//cout << endl;
			}
		}
		currtime += bias;

		//load all new intervals / close all old ones, according to the actions at currtime
		while(events[curridx].time == currtime){
			// if an ending event:
			if(events[curridx].action==1){
				if(intervals[events[curridx].id].cost > 0){
					cout << "NIE" << endl;
					return 0;
				}
			}
			//if a starting event
			else{
				open_intervals.insert(std::upper_bound (open_intervals.begin(), open_intervals.end(), events[curridx].id, compare_ends),
						events[curridx].id);
			}
			curridx++;
		}
	}
	cout << "TAK";// << endl;
	return 0;
}