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
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

struct InputLine {
    int p, k, c;
};

/*struct TimePoint {
    TimePoint() {
        begs = 0;
        ends = 0;
        units = 0;
    }

    int begs;
    int ends;
    int units;
};*/

class ProblemSolver {
public:
    ProblemSolver() {
        input = 0;
        units = 0;
    }

    ~ProblemSolver() {
        if (input)
            delete [] input;
        if (units)
            delete [] units;
    }

    void readData() {
        cin >> n >> m;
        input = new InputLine[n];
        maxT = 0;
        for (int i = 0; i < n; ++i) {
            cin >> input[i].p >> input[i].k >> input[i].c;
            if (input[i].k > maxT)
                maxT = input[i].k;
        }
    }

    void fillTime() {
        units = new int[maxT+2];
        for (int i = 0; i <= maxT + 1; ++i)
            units[i] = 0;

        for (int i = 0; i < n; ++i) {
            timeToBegs[input[i].p].push_back(&input[i]);
            timeToEnds[input[i].k].push_back(&input[i]);
            for (int t = input[i].p; t < input[i].p + input[i].c; ++t)
                units[t]++;
            //units[input[i].p] += input[i].c;
        }
    }

    bool solve() {
        fillTime();

        int maxWork = 0;
        int workRequired = 0;
        int openedTasks = 0;
        for (int t = 0; t <= maxT; t++) {
            //cerr << "Work done to time " << t << ": " << maxWork << endl;

            const vector<InputLine*>& ends = timeToEnds[t];
            for (const InputLine* line: ends) {
                workRequired += line->c;
                openedTasks--;
            }
            //cerr << "Work required to time " << t << ": " << workRequired << endl;
            if (workRequired > maxWork)
                return false;

            const vector<InputLine*>& begs = timeToBegs[t];
            for (const InputLine* line: begs) {
                openedTasks++;
            }

            int computingPower = min(openedTasks, m);
            if (computingPower < units[t]) {
                int shift = units[t] - computingPower;
                units[t+1] += shift;
                maxWork += computingPower;
            } else {
                maxWork += units[t];
            }
            units[t] = 0;
        }
        return true;
    }

    int n, m;
    int maxT;
    InputLine* input;
    unordered_map<int, vector<InputLine*>> timeToBegs;
    unordered_map<int, vector<InputLine*>> timeToEnds;
    int* units;
};

int main() {
    ios_base::sync_with_stdio(0);

    ProblemSolver solver;
    solver.readData();
    bool r = solver.solve();
    if (r)
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;

    return 0;
}