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

constexpr int MAXN = 101;
constexpr int INF = 2147483647;
int n, m;

int end_time[MAXN];
int time_left[MAXN];

struct Event {
    int num;
    int time;
    bool start;

    Event(int num_, int time_, bool start_) : num(num_), time(time_), start(start_)
    {}
    Event() : Event(0, 0, false) {}

    bool operator<(const Event& other) const {
        if (time != other.time) {
            return time < other.time;
        }
        return num < other.num;
    }
};


int curr_time = 0;

int margin(int a) {
    return end_time[a] - curr_time - time_left[a];
}

bool cmp(int a, int b) {
    int t1 = margin(a);
    int t2 = margin(b);
    if (t1 != t2) {
        return t1 < t2;
    }
    return a < b;
}

std::vector<int> ready_tasks;

std::vector<Event> events;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        int st, en, time_req;
        scanf("%d%d%d", &st, &en, &time_req);
        end_time[i] = en;
        events.emplace_back(i, st, true);
        time_left[i] = time_req;
    }
    std::sort(events.begin(), events.end());
    auto events_it = events.begin();

//     for (auto& ev : events) {
//         printf("%d %d\n", ev.num, ev.time);
//     }

    bool ok = true;

    while (events_it != events.end() || !ready_tasks.empty()) {

//         printf("t = %d\n", curr_time);
//         for (int x : ready_tasks) {
//             printf("%d end %d left %d margin %d\n", x, end_time[x], time_left[x], margin(x));
//         }
//         printf("------\n");

        while (events_it != events.end() && events_it->time == curr_time) {
            ready_tasks.push_back(events_it->num);
            ++events_it;
        }

        int next_time = events_it == events.end() ? INF : events_it->time;
        for (int task_no : ready_tasks) {
            next_time = std::min(next_time, time_left[task_no] + curr_time);
        }
        if (ready_tasks.size() > m) {
            next_time = std::min(next_time, curr_time + std::max(1, margin(ready_tasks[m - 1]) - margin(ready_tasks[m])));
        }

        std::sort(ready_tasks.begin(), ready_tasks.end(), cmp);

//         printf("next time %d\n", next_time);
//         for (int x : ready_tasks) {
//             printf("%d end %d left %d margin %d\n", x, end_time[x], time_left[x], margin(x));
//         }
//         printf("------\n\n");

        auto ready_it = ready_tasks.begin();
        for (int i = 0; i < m && ready_it != ready_tasks.end(); ++i) {
            time_left[*ready_it] -= next_time - curr_time;
            ++ready_it;
        }

        curr_time = next_time;

//         printf("********\n");
//         for (int x : ready_tasks) {
//             printf("%d end %d left %d margin %d\n", x, end_time[x], time_left[x], margin(x));
//         }
//         printf("------\n\n\n");

        for (int i = 0; i < ready_tasks.size(); ++i) {
            if (time_left[ready_tasks[i]] == 0) {
                if (curr_time > end_time[ready_tasks[i]]) {
                    printf("NIE\n");
                    return 0;
                }

                std::swap(ready_tasks[i], ready_tasks[ready_tasks.size() - 1]);
                ready_tasks.pop_back();
            }
        }
    }

    printf("TAK\n");
    return 0;
}