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
#include <bits/stdc++.h>
using namespace std;
const int N=105, INF=1e9+5, M=1e6+5;
int p[N], k[N], c[N], old_c[N];
int proc_cnt[M], cpu_cnt[M];
inline bool compare(int i, int j)
{
    return proc_cnt[i]-cpu_cnt[i]<proc_cnt[j]-cpu_cnt[j];
}
inline bool compare_tasks(int i, int j)
{
    return k[i]-c[i]<k[j]-c[j];
}
int tmp[N];
inline void easy_sort(vector<int> &v, int m)
{
    merge(v.begin(), v.begin()+m, v.begin()+m, v.end(), tmp, compare_tasks);
    copy(tmp, tmp+v.size(), v.begin());
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; ++i) scanf("%d%d%d", &p[i], &k[i], &c[i]);
    int mx=*max_element(k, k+n);
    fill(cpu_cnt, cpu_cnt+mx, m);
    vector<int> v(mx);
    for(int i=0; i<mx; ++i) v[i]=i;
    for(int i=0; i<n; ++i) for(int j=p[i]; j<k[i]; ++j) ++proc_cnt[j];
    sort(v.begin(), v.end(), compare);
    bool ok=0, tak=1;
    copy(c, c+n, old_c);
    for(int i=0; i<n; ++i)
    {
        vector<int> affected, unaffected;
        for(int j: v)
        {
            if(j>=p[i]&&j<k[i])
            {
                --proc_cnt[j];
                if(cpu_cnt[j]>0&&c[i]>0)
                {
                    --c[i];
                    --cpu_cnt[j];
                    unaffected.push_back(j);
                }
                else affected.push_back(j);
            }
            else unaffected.push_back(j);
        }
        if(c[i]>0) tak=0;
        merge(affected.begin(), affected.end(), unaffected.begin(), unaffected.end(), v.begin(), compare);
    }
    if(tak) ok=1;
    tak=1;
    vector<int> active;
    copy(old_c, old_c+n, c);
    for(int t=0; t<=mx; ++t)
    {
        for(int i=0; i<n; ++i)
        {
            if(p[i]==t)
            {
                active.push_back(i);
                sort(active.begin(), active.end(), compare_tasks);
            }
            if(t>k[i]-c[i]) tak=0;
            if(c[i]==0)
            {
                c[i]=-INF;
                sort(active.begin(), active.end(), compare_tasks);
            }
        }
        if(active.size()>0) easy_sort(active, min(m, (int)active.size()));
        for(int i=0; i<m&&i<active.size(); ++i) --c[active[i]];
    }
    if(tak) ok=1;
    printf(ok ? "TAK\n" : "NIE\n");
}