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 <cstdio>
#include <tuple>
#include <list>
#include <vector>

// start, free time, left time
typedef std::tuple<int, int, int> i_triple;
// free time, left time
typedef std::tuple<int, int> i_double;


int m, n;
int p, k, c;


bool predicate(const i_double& x) {
    return std::get<1>(x) == 0;
}

int main() {
    scanf("%d %d", &n, &m);


    std::list<i_triple> new_procs;
    std::list<i_double> procs;

    std::list<i_double> front;
    std::list<i_double> moved;
    std::list<i_double> back;

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &p, &k, &c);
        new_procs.push_back(std::make_tuple(p, k - p - c, c));
    }

    new_procs.sort();

    std::list<i_double> merged;
    int free, dur;

    for (int i = 0; !new_procs.empty() || !procs.empty(); i++) {
        if (new_procs.size() + procs.size() <= m) break;

        // wrzucenie kolejnych do worka
        while (!new_procs.empty() && std::get<0>(new_procs.front()) == i) {
            free = std::get<1>(new_procs.front());
            dur = std::get<2>(new_procs.front());
            merged.push_back(std::make_tuple(free, dur));
            new_procs.pop_front();
        }

        // scalenie dwóch list
        std::list<i_double>::iterator it = procs.begin();
        while (!merged.empty()) {
            if (it == procs.end() || (*it) > merged.front()) {
                procs.insert(it, merged.front());
                merged.pop_front();
            }
            else {
                ++it;
            }
        }

        if (procs.empty()) continue;

        // obsłużenie pierwszych procesów
        it = procs.begin();
        auto first_different = it;
        int diff_val = std::get<0>(*it);
        for (int j = 0; j < m && it != procs.end(); j++) {
            i_double& p = *it;
            if (std::get<0>(p) != diff_val) {
                first_different = it;
                diff_val = std::get<0>(p);
            }
            std::get<1>(p)--;
            ++it;
        }
        front.splice(front.begin(), procs, procs.begin(), first_different);
        back.splice(back.begin(), procs, first_different, it);

        // nieobsłużenie w terminie procesu
        if (it != procs.end() && std::get<0>(*it) == 0) {
            printf("NIE\n");
            return 0;
        };

        auto first_same = it;
        // skrócenie wolnego nieobsłużonym o tej samej wartości
        while (it != procs.end() && std::get<0>(*it) == diff_val) {
            std::get<0>(*it)--;
            ++it;
        }

        moved.splice(moved.begin(), procs, first_same, it);
        // skrócenie wolnego nieobsłużonym
        while (it != procs.end()) {
            i_double& p = *it;
            std::get<0>(p)--;
            ++it;
        }

        back.splice(back.end(), procs);
        front.remove_if(predicate);
        back.remove_if(predicate);

        // łączenie list
        procs.splice(procs.begin(), front);
        procs.splice(procs.end(), moved);
        procs.splice(procs.end(), back);
    }

    printf("TAK\n");

    return 0;
}