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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

#define N 107
#define st first
#define nd second
#define pb push_back

using namespace std;

bool czyrobimy[N];
int n, ileproc, akt_poz;
int zerowe_w_obs;
int ilezostalo[N], start[N], koniec[N]; // odnosi sie do procesow od 0 do n - 1
vector<pair<int, int> > start_nr;
priority_queue<pair<int, int> > koniec_nr_nieobs;// rosnace koncami | wrzucone ujemne wartosci koncow
priority_queue<pair<int, int> > koniec_nr_obs; // malejace koncami 

int main()
{
	scanf("%d%d", &n, &ileproc);
	
	for(int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &start[i], &koniec[i], &ilezostalo[i]);
		start_nr.pb(make_pair(start[i], i));
	}
	
	sort(start_nr.begin(), start_nr.end());
	
	koniec_nr_obs.push(make_pair(koniec[start_nr[0].nd], start_nr[0].nd));
	czyrobimy[start_nr[0].nd] = 1;
	akt_poz = start_nr[0].st;/*
	for(int i = 0;i < n; i++)
		printf("%d %d\n", start_nr[i].st, start_nr[i].nd);
	*/
	for(int i = 1; i <= start_nr.size(); i++)
	{
		int roznica;
		if(i == start_nr.size())
			roznica = 1000007;
		else
			roznica = start_nr[i].st - start_nr[i - 1].st;
		
		//robienie aktualnych procesow od start (i - 1) do start (i) dodajac nowe jak ktorys sie skonczy
		while(roznica > 0)
		{/*
			//DODATEK HEURO IF'OW
			if(!koniec_nr_nieobs.empty())
			{
				
				int minzost = 1000007, ilemin = 0, drugiemin = 1000007, rozmiar = koniec_nr_obs.size(), tab[N][2];// 0 - st 1 - nd
				for(int j = 0; j < rozmiar; j++)
				{
					int h1 = koniec_nr_obs.top().st, h2 = koniec_nr_obs.top().nd;
					tab[j][0] = h1;
					tab[j][1] = h2;
					koniec_nr_obs.pop();
					if(ilezostalo[h2] < minzost && ilezostalo[h2] > 0)
					{
						drugiemin = minzost;
						ilemin = 1;
						minzost = ilezostalo[h2];
					}
					if(ilezostalo[h2] == minzost)
						ilemin++;
				}
				int flag = 0;
				for(int j = 0; j < rozmiar; j++)
				{
					if((roznica >= minzost * 2 && ilemin > 1) || (roznica >= minzost + drugiemin && ilemin == 1))
					{
						if(!flag && ilezostalo[tab[j][1]] == minzost)
						{
							printf("arr%d", akt_poz);
							flag = 1;
							czyrobimy[tab[j][1]] = 0;
							czyrobimy[koniec_nr_nieobs.top().nd] = 1;
							koniec_nr_obs.push(make_pair(-koniec_nr_nieobs.top().st, koniec_nr_nieobs.top().nd));
							koniec_nr_nieobs.pop();
							koniec_nr_nieobs.push(make_pair(-tab[j][0], tab[j][1]));
							continue;
						}
					}
					koniec_nr_obs.push(make_pair(tab[j][0], tab[j][1]));
				}
				//printf("%d %d", koniec_nr_obs.top().st, koniec_nr_obs.top().nd);
			}
			*/
			//KONIEC
			
			int minodj = 1000007;
			for(int j = 0; j < n; j++)
			{
				if(czyrobimy[j])
				{
					minodj = min(minodj, ilezostalo[j]);
					//printf("czy%d ", j);
				}
			}
			
			minodj = min(minodj, roznica);
			akt_poz += minodj;
			//if(i == start_nr.size())
			//	printf("minodj: %d\n", minodj);
			for(int j = 0; j < n; j++)
			{
				if(czyrobimy[j])
				{
					ilezostalo[j] -= minodj;
					if(ilezostalo[j] == 0)
					{
						czyrobimy[j] = 0;
						zerowe_w_obs++;
						
						//jest zle
						if(koniec[j] < akt_poz)
						{
							//printf("\npsuje: %d", j);
							printf("NIE");
							return 0;
						}
						
					}
				}
			}
			
			while(koniec_nr_obs.size() < ileproc + zerowe_w_obs)
			{
				if(koniec_nr_nieobs.size() == 0)
					break;
				//dodajemy z nieobs do obs
				czyrobimy[koniec_nr_nieobs.top().nd] = 1;
				koniec_nr_obs.push(make_pair(-koniec_nr_nieobs.top().st, koniec_nr_nieobs.top().nd));
				koniec_nr_nieobs.pop();
				//printf("pizza2");
			}
			
			roznica -= minodj;
		}/*
		printf("obrot:%d zostalo: ", i);
		for(int j = 0; j < n; j++)
			printf("%d ", ilezostalo[j]);
		printf("\n");*/
		//rozpatrywanie nowego startujacego procesu
		
		koniec_nr_nieobs.push(make_pair(-koniec[start_nr[i].nd], start_nr[i].nd));
		//printf("wrzucamnieobs:%d %d\n", koniec_nr_nieobs.top().st, koniec_nr_nieobs.top().nd);
		
			//usuwamy zerowe z obs
			while(!koniec_nr_obs.empty() && ilezostalo[koniec_nr_obs.top().nd] == 0)
			{
				koniec_nr_obs.pop();
				zerowe_w_obs--;
			}
			//dodajemy z nieobs do obs do full
			while(koniec_nr_obs.size() < ileproc + zerowe_w_obs)
			{
				if(koniec_nr_nieobs.empty())
					break;
				
				czyrobimy[koniec_nr_nieobs.top().nd] = 1;
				koniec_nr_obs.push(make_pair(-koniec_nr_nieobs.top().st, koniec_nr_nieobs.top().nd));
				koniec_nr_nieobs.pop();
			}
			//jezeli w nieobs sa z wczesniejszym koncem zamieniamy z obs
			while(!koniec_nr_nieobs.empty() && 
			-koniec_nr_nieobs.top().st < koniec_nr_obs.top().st)
			{
				czyrobimy[koniec_nr_nieobs.top().nd] = 1;
				czyrobimy[koniec_nr_obs.top().nd] = 0;
				
				int p1 = -koniec_nr_obs.top().st, p2 = koniec_nr_obs.top().nd;
				koniec_nr_obs.pop();
				koniec_nr_obs.push(make_pair(-koniec_nr_nieobs.top().st, koniec_nr_nieobs.top().nd));
				koniec_nr_nieobs.pop();
				koniec_nr_nieobs.push(make_pair(p1, p2));
				//moga sie pojawic zerowe po zamianie wiec usuwamy
				while(!koniec_nr_obs.empty() && ilezostalo[koniec_nr_obs.top().nd] == 0)
				{
					koniec_nr_obs.pop();
					zerowe_w_obs--;
				}
			}
			/*
			if(!koniec_nr_obs.empty())
				printf("koniecobs:%d %d\n", koniec_nr_obs.top().st, koniec_nr_obs.top().nd);
			if(!koniec_nr_nieobs.empty())
				printf("koniecnieobs:%d %d\n", koniec_nr_nieobs.top().st, koniec_nr_nieobs.top().nd);
			*/
	}
	
	for(int i = 0; i < n; i++)
	{
		if(ilezostalo[i] != 0)
		{
			printf("NIE");
			return 0;
		}
	}
	printf("TAK");
	
	return 0;
}