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

#define iter multiset< pair<int,int> >::iterator

using namespace std;

// priorytet = koniec - czas potrzebny na wykonanie
// im nizszy, tym pilniejsze zadanie
// priorytet rowny obecnemu czasowi oznacza koniecznosc natychmiastowego wykonania
int ilezadan, procesory;
int lacznyczas; // czas w trakcie ktorego wykonuja sie wszystkie zadania
int pocz, kon, czas, priorytet;
vector< pair<int,int> > nowezadania[1000005]; // nowe zadania w i-tej sekundzie; zadania w formie (priorytet, czas)
multiset< pair<int,int> > zadania; // aktualne zadania; zadania w formie (priorytet, pozostaly czas)
int jeszczemoge; // ile jeszcze mam dostepnego czasu procesorow
int konieczne; // ile zadan musi zostac wykonanych w tym momencie
vector< pair<int,int> > dowrzucenia; // wykonane zadania wrzucam do seta na sam koniec zeby nie odczytywac ich dwa razy

int main()
{
    scanf("%d%d",&ilezadan,&procesory);
    for(int i=0; i<ilezadan; i++)
    {
        scanf("%d%d%d",&pocz,&kon,&czas);
        priorytet = kon - czas;
        lacznyczas = max(lacznyczas, kon);
        nowezadania[pocz].push_back(make_pair(priorytet, czas));
    }
    for(int i=0; i<=lacznyczas; i++)
    {
        for(int j=0; j<nowezadania[i].size(); j++)
            zadania.insert(nowezadania[i][j]);
        /*printf("[%d]",i);
        for(iter it=zadania.begin(); it!=zadania.end(); it++)
            printf("(%d,%d)",(*it).first,(*it).second);
        printf("\n");*/

        jeszczemoge = procesory;
        konieczne = 0;
        while(zadania.begin() != zadania.end())
        {
            iter it = zadania.begin();
            priorytet = (*it).first; czas = (*it).second;
            if(priorytet <= i)
            {
                konieczne++;
                if(konieczne > procesory)
                {
                    printf("NIE\n");
                    return 0;
                }
            }
            if(jeszczemoge == 0)
                break;
            if(czas > 1)
            {
                jeszczemoge--;
                zadania.erase(it);
                dowrzucenia.push_back(make_pair(priorytet+1,czas-1));
            }
            if(czas == 1)
            {
                jeszczemoge--;
                zadania.erase(it);
            }
        }
        iter it = zadania.begin();
        for(int j=0; j<dowrzucenia.size(); j++)
            it = zadania.insert(it, dowrzucenia[j]);
        dowrzucenia.clear();
    }
    printf("TAK\n");
	return 0;
}