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
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <set>
#include <time.h>       /* time */
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;
struct Task{
  bool operator<(const Task& t) const {
    return this->start<t.start;
  }
  int start;
  int end;
  int size;
  int size2;
};
struct TaskCompare {
  bool operator()(const Task* t1, const Task* t2) {
    return (t1->end - t1->size) > (t2->end - t2->size);
  }
};
int main(int argc, char **argv){
  int n,m;
  vector<Task> tasks;
  scanf("%d %d", &n, &m);
  int max_end;
  for(int i=0;i<n;i++){
    Task t;
    scanf("%d %d %d",&t.start, &t.end, &t.size);
    max_end = max(t.end,max_end);
    t.size2 = t.size;
    tasks.push_back(t);
  }
  sort(tasks.begin(), tasks.end());
  int t = tasks.begin()->start;
  TaskCompare cmp;
  priority_queue<Task*,vector<Task*>, TaskCompare> q;
  int task_it=0;
  for(int t=0;t<max_end;t++){
    while(task_it<tasks.size() && tasks[task_it].start<=t){
      q.push(&tasks[task_it]);
      task_it++;
    }
    if(q.empty()) {
      if (task_it < tasks.size()) {
        t = tasks[task_it].start-1;
        continue;
      } else {
        break;
      }
      
    }
    vector<Task*> to_process;
    for(int j = 0; j<m; j++) {
      if (!q.empty()){
        to_process.push_back(q.top());
        q.pop();
      }
    }
    int next_start = task_it < tasks.size()?tasks[task_it].start:INT_MAX;
    int min_size=(*to_process.begin())->size;
    for(int j = 1; j<to_process.size(); j++) {
      min_size = min(min_size, to_process[j]->size);
    }
    int steps = min(min_size, next_start-t);
    if(!q.empty()) {
      if(q.top()->end - q.top()->size <= t) {
        printf("NIE");
        return 0;
      }
      steps = min(steps, q.top()->end - q.top()->size - t);
    }
    t += (steps-1);
    for(int j=0;j<to_process.size();j++){
      if (to_process[j]->end<=t) {
          printf("NIE");
          return 0;
        }
      to_process[j]->size-=steps;
      if(to_process[j]->size>0){
        q.push(to_process[j]);
      }
    }
  }
  if(q.empty()) {
    printf("TAK");
  } else {
    printf("NIE");
  }
  return 0;
}