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
//Lukasz Janeczko Krakow
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    int n, m, it=2100000000, last=0;
    scanf("%d %d",&n,&m);
    vector < pair <int,int> > Processes(n); vector < pair <int,int> > Starts(n+1);
    for(int i=0; i<n; i++)
        {
            scanf("%d",&Starts[i].first);
            Starts[i].second=i;
            it=min(it,Starts[i].first);
            scanf("%d",&Processes[i].second);
            last=max(last,Processes[i].second);
            scanf("%d",&Processes[i].first);
        }
    Starts[n]={2100000000,2100000000};
    sort(Starts.begin(),Starts.end());
    int ind=0, j, s, v; bool bad=false; vector < pair <int,int> > Waiting(n);
    priority_queue < pair <int,int> > Q;
    while(it<=last && !bad)
        {
            j=0;
            while(Starts[ind].first==it)
                {
                    v=Starts[ind].second;
                    Q.push({(-1)*(Processes[v].second-Processes[v].first-Starts[ind].first),v});
                    ind++;
                }
            s=Q.size();
            //cout << it << " " << ind << " " << Starts[ind].first << " " << s << " " << last <<endl;
            s=min(s,m);
            for(int k=0; k<s && !bad; k++)
                {
                    pair <int,int> r=Q.top();
                    Q.pop();
                    //cout << r.first << " " << r.second << " " << Processes[r.second].first << " " << Processes[r.second].second <<endl;
                    if(r.first>0)
                        bad=true;
                    Processes[r.second].first--;
                    if(Processes[r.second].first!=0)
                        {
                            Waiting[j]=r;
                            j++;
                        }
                }
            if(!Q.empty())
                {
                    while(!Q.empty())
                        {
                            pair <int,int> r=Q.top();
                            Q.pop();
                            r.first++;
                            if(r.first>0)
                                bad=true;
                            else
                                {
                                    Waiting[j]=r;
                                    j++;
                                }
                        }
                }
            for(int f=0; f<j; f++)
                Q.push(Waiting[f]);
            it++;
        }
    if(bad)
        printf("NIE\n");
    else
        printf("TAK\n");
    return 0;
}