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
#include <iostream>
#include <algorithm>

using namespace std;

struct Zadanie{
    int poczatek;
    int koniec;
    int czas;
};

struct Pozycja{
    int koniec;
    int czas;
};

bool operator<(const Zadanie& l, const Zadanie& r)
{
  return l.poczatek < r.poczatek;
}

bool operator<(const Pozycja& l, const Pozycja& r)
{
  return l.koniec < r.koniec;
}

int main() {
	int maks = 1000000 + 5;
	int n;  // ilosc zadan
	cin >> n;
	int m;  // ilosc procesorow
	cin >> m;
	
	// moze ilosc procesorow wystarczy?
    if (n <= m){
		cout << "TAK";
		return 0;
	}
	// Lista zadan
	 Zadanie zadania[101];
	 // wskaznik do listy zadan
	 int wskZad = 0;
	 
	 // wczytujemy zadania 
	 for (int i=0; i<n; i++){
		 cin >> zadania[i].poczatek >> zadania[i].koniec >> zadania[i].czas;
	 }
	 
	 // wartownik
	zadania[n].poczatek = maks;
	zadania[n].koniec = maks;
	zadania[n].czas = 1;
	
	// sortujemy wg poczatkow obslugi
	sort(zadania, zadania + n);
		
	//skaner, miejsce przechowywania zadan aktualnie przetwarzanych
	Pozycja skaner[101];
	int ileSkan = 0;  // ile zadan aktualnie sprawdza skaner(jest w skanerze); 0 - skaner pusty
	int ileZostalo = n;  // ile zadan zostalo do obsluzenia (jest w skanerze lub jeszcze czeka na swoja kolejke)
	
	// ZACZYNAMY
    int wskCzasu = zadania[0].poczatek;  // chwila rozpoczecia obslugi zadan
	
	while (wskCzasu < maks){
		// ew. pobieramy pozycje z listy zadan
		// gdy dodalismy nowe pozycje trzeba posortowac skaner
		bool dodano = false;
		while (wskCzasu == zadania[wskZad].poczatek){
			skaner[ileSkan].koniec = zadania[wskZad].koniec;
			skaner[ileSkan].czas = zadania[wskZad].czas;
			ileSkan++;
			wskZad++;
			dodano = true;
		}
		if (dodano) sort(skaner, skaner+ileSkan);
			
		//dla pierwszych n pozycji zmniejszamy czas o 1
		//gdy czas zmniejszymy do zera trzeba dokonac korekty
		int iks = ileSkan;
		if (iks > m) iks = m;
		int zmieniono = 0;
		for(int j=0; j<iks; j++){
			skaner[j].czas--;
			if (skaner[j].czas == 0){
				skaner[j].koniec = maks;
				zmieniono++;
			}
		}
		if (zmieniono > 0){
			sort(skaner, skaner+ileSkan);
			ileSkan = ileSkan - zmieniono;
			ileZostalo = ileZostalo - zmieniono;
		}
				
		//gdy ileZostalo == 0 to SUKCES
		if (ileZostalo == 0){
			cout << "TAK";
			return 0;
		}
		
		//gdy czas sie skonczyl a pozycja maja czas wiekszy od zera to KICHA
		if ((ileSkan >0) and (skaner[0].koniec == wskCzasu)){
			cout << "NIE";
			return 0;
		}
		
		wskCzasu++;
		if (ileSkan == 0){
			wskCzasu = zadania[wskZad].poczatek;
		}
	}
//	cout << "NIE";
//	return 0;
	
}