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
#include <cstdio>
#include <queue>
#include <unordered_set>
#include <algorithm>

const int MILION = 2000000000;

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

struct task {
  int start, end;
  int time;
  int gap;
  int id;
};

task* sorted[200];

task T[200];
std::priority_queue<int, std::vector<int>, std::greater<int> > events;
std::unordered_set<int> running;

bool order(const task* a, const task* b) {
  if(a->gap != b->gap) return a->gap < b->gap;
  if(a->end != b->end) return a->end < b->end;
  return a->time > b->time;
}

main() {
  scanf("%d %d", &n, &m);
  for(int i=0;i<n;i++) {
    scanf("%d %d %d", &p, &k, &c);
    T[i].start = p;
    T[i].end = k;
    T[i].time = c;
    T[i].id = i;
    events.push(p);
    events.push(k);
    sorted[i] = &T[i];
  }

  int last_event = -1;
  while(!events.empty()) {
    int event = events.top();
    events.pop();
//    printf("%d\n", event);
    if(event == last_event) continue;

//    printf("GO\n");
//    for(int i=0;i<n;i++) {
//      printf("%d %d %d %d\n", T[i].start, T[i].end, T[i].time, T[i].gap);
//    }

    int t = event - last_event;
    for (const auto& r : running) {
      T[r].time-=t;
    }
    running.clear();
    r = 0;

    last_event = event;

    for(int i=0;i<n;i++) {
      if(T[i].time == 0)
        continue;
      T[i].gap = T[i].end - event - T[i].time;
//      printf("GAP: %d\n", T[i].gap);
      if(T[i].gap < 0) {
        printf("NIE\n");
        return 0;
      }
    }
    std::sort(sorted, sorted+n, order);
    for(int i=0;i<n;i++) {
      if (sorted[i]->time == 0 || sorted[i]->start > event)
        continue;
      if(r < m) {
        running.insert(sorted[i]->id);
        events.push(event+sorted[i]->time);
        r++;
      } else {
        events.push(event+sorted[i]->gap);  // when this task cannot wait anymore
      }
    }
  }
  printf("TAK\n");

  return 0;
}