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

// #define DEBUGPRINT

using namespace std;

int t, n, m, maxT;

struct entry {
    int p;
    int k;
    int c;
    int computed;
    inline int preFunc() const { return k-p-c; }
    inline bool didntFinish() const { return k <= t; }
    inline int func() const { return (k-t)-(c-computed); }
    inline bool finished() const { return computed == c; }
};

//entry[] entries;

deque<entry> waiting;
deque<entry> updating;
deque<entry> current;
deque<entry> future;

inline bool preComp(  const entry& f, const entry& s){
    return f.p != s.p
    ? f.p < s.p
    : f.preFunc() < s.preFunc();
}

inline bool comp(const entry& f, const entry& s) {
    return f.func() < s.func();
}

inline bool fillUpdating(){
    for(int i = 0; i < m; ++i){

        if( waiting.size() > 0 && waiting.front().didntFinish() || current.size() > 0 && current.front().didntFinish()){
            printf("NIE\n"); return true;;
           }

        if( waiting.size() > 0 && waiting.front().p <= t && (
            current.size() == 0 || comp(waiting.front(), current.front())
        )){
            updating.push_back(waiting.front());
            waiting.pop_front();
        } else if( current.size() > 0 ){
            updating.push_back(current.front());
            current.pop_front();
        } else {
            break;
        }
    }

    return false;
}

inline void updateUpdating(){
    for( deque<entry>::iterator it = updating.begin(); it < updating.end(); it++){
        it->computed += 1;
#ifdef DEBUGPRINT
cerr << "updated: " << it->p << " " << it->k << " " << it->c << " computed: "<<  it->computed <<"\n";
#endif // DEBUGPRINT
    }
}

inline void mergeToFuture(){
        while( updating.size() != 0 || current.size() != 0 || waiting.size() > 0 && waiting.front().p <= t){
            if( updating.size() > 0 && updating.front().finished()){
#ifdef DEBUGPRINT
cerr << "finished: " << updating.front().p << " " << updating.front().k << " " << updating.front().c << "\n";
#endif // DEBUGPRINT
                updating.pop_front();
            } else if( waiting.size() > 0 && waiting.front().p <= t &&
                (current.size() == 0 || comp(waiting.front(), current.front())) &&
                (updating.size() == 0 || comp(waiting.front(), updating.front())) ){
                future.push_back(waiting.front());
                waiting.pop_front();
            } else if( updating.size() > 0 && (
                current.size() == 0 || comp(updating.front(), current.front())
            )){
                future.push_back(updating.front());
                updating.pop_front();
            } else if( current.size() > 0 ){
                future.push_back(current.front());
                current.pop_front();
            } else {
                break;
            }
        }
}

int main() {
    scanf("%i %i", &n, &m);
    waiting.resize(n);
    t = 10000000;
    maxT = 0;
    for(int i = 0; i < n; ++i){
        scanf("%i %i %i", &waiting[i].p, &waiting[i].k, &waiting[i].c);
        waiting[i].computed = 0;
        t = min(t, waiting[i].p);
        maxT = max(maxT, waiting[i].k);
    }

    sort(waiting.begin(), waiting.end(), preComp);

#ifdef DEBUGPRINT
for(int i = 0 ; i < n; i++ ) cerr << "afterSort: " << waiting[i].p << " " << waiting[i].k << " " << waiting[i].c << "\n";
#endif // DEBUGPRINT

    for(; t <= maxT; ++t){
        if(waiting.size() == 0 && current.size() == 0)
            break;

        if(fillUpdating()) return 0;

        updateUpdating();

        mergeToFuture();

        future.swap(current);
    }

    printf("TAK\n");

	return 0;
}