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
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class sze {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Task[] tasks = new Task[n];

        int minP = Integer.MAX_VALUE, maxK = Integer.MIN_VALUE, len = 0;
        for (int i = 0; i < n; i++) {
            int p = scanner.nextInt();
            int k = scanner.nextInt();
            int c = scanner.nextInt();

            if (p < minP) {
                minP = p;
            }
            if (k > maxK) {
                maxK = k;
            }
            len += c;

            tasks[i] = new Task(p, k, c);
        }

        // Too much work
        if ((maxK - minP) * m < len) {
            System.out.println("NIE");
            return;
        }

        Comparator<Task> deltaComparator = (o1, o2) -> o1.delta - o2.delta;
        Task[] prioritizedTasks = new Task[n];
        Task[] prioritizedTasksTmp = new Task[n];
        Task[] prioritizedTasksBuf;
        int prioritizedTaskIdx;
        int prioritizedTaskTmpIdx = 0;

        // Sort tasks by possible starting point
        Arrays.sort(tasks, (o1, o2) -> o1.p - o2.p);

        boolean prioritize = false;
        int taskIdx = 0, tasksCompleted = 0;
        for (int i = minP; i <= maxK; ++i) {

            prioritizedTasksBuf = prioritizedTasks;
            prioritizedTasks = prioritizedTasksTmp;
            prioritizedTasksTmp = prioritizedTasksBuf;

            prioritizedTaskIdx = prioritizedTaskTmpIdx;
            prioritizedTaskTmpIdx = 0;

            while (taskIdx < n && tasks[taskIdx].p == i) {
                prioritizedTasks[prioritizedTaskIdx++] = tasks[taskIdx++];
                prioritize = true;
            }

            if (prioritize) {
                Arrays.sort(prioritizedTasks, 0, prioritizedTaskIdx, deltaComparator);
            }

            prioritize = false;
            int procIdx = 0;
            for (int j = 0; j < prioritizedTaskIdx; j++) {
                Task task = prioritizedTasks[j];

                if (i >= task.k) {
                    System.out.println("NIE");
                    return;
                }
                if (procIdx < m) {
                    task.c -= 1;
                    if (task.c == 0) {
                        // Task completed
                        tasksCompleted += 1;
                        if (tasksCompleted == n) {
                            System.out.println("TAK");
                            return;
                        }
                    } else {
                        prioritizedTasksTmp[prioritizedTaskTmpIdx++] = task;
                    }
                } else {
                    task.delta -= 1;
                    if (task.delta < 0) {
                        System.out.println("NIE");
                        return;
                    }
                    // Update task
                    prioritizedTasksTmp[prioritizedTaskTmpIdx++] = task;
                    prioritize = true;
                }
                procIdx += 1;
            }
        }

        System.out.println(prioritizedTaskTmpIdx == 0 ? "TAK" : "NIE");
    }

    static class Task {
        int p;
        int k;
        int c;
        int delta;

        Task(int pp, int kk, int cc) {
            p = pp;
            k = kk;
            c = cc;
            delta = k - p - c;
        }

        @Override
        public String toString() {
            return "P: " + p + " K: " + k + " C: " + c + " D: " + delta;
        }
    }
}