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
#include <iostream>
 #include <stdio.h>
 using namespace std;

  int maxTemperature = 1000002;
  long long volumePerTemperature[1000002];

  void prepareData() {
    for (int temperature = 0; temperature < maxTemperature; temperature++) {
      volumePerTemperature[temperature] = 0;
    }

    int numberOfPeople;
    cin >> numberOfPeople;

    for (int i = 0; i < numberOfPeople; i++) {
      long long volume;
      long long presentTemperature;
      long long futureTemperature;
      cin >> volume;
      cin >> presentTemperature;
      cin >> futureTemperature;

      volumePerTemperature[(int) presentTemperature] += volume;
      volumePerTemperature[(int) futureTemperature] -= volume;
    }
  }

  void runMain() {
    // from left
    long long volumeBalance = 0;
    long long heatBalance = 0;
    long long lastVisitedTemperature = 0;
    for (int temperature = 0; temperature < maxTemperature; temperature++) {
      long long volume = volumePerTemperature[temperature];
      if (volume != 0) {
        long long deltaTemperature = temperature - lastVisitedTemperature;
        heatBalance += volumeBalance * deltaTemperature;
        volumeBalance += volume;
        lastVisitedTemperature = temperature;

        if (heatBalance < 0) {
          printf("NIE\n");
          return;
        }
      }
    }

    // from right
    volumeBalance = 0;
    heatBalance = 0;
    lastVisitedTemperature = 0;
    for (int temperature = maxTemperature - 1; temperature >= 0; temperature--) {
      long long volume = volumePerTemperature[temperature];
      if (volume != 0) {
        long long deltaTemperature = lastVisitedTemperature - temperature; // delta always positive
        heatBalance += volumeBalance * deltaTemperature;
        volumeBalance += volume;
        lastVisitedTemperature = temperature;

        if (heatBalance < 0) { // because delta positive
          printf("NIE\n");
          return;
        }
      }
    }

    // no imbalances found
    printf("TAK\n");
  }

  int main() {
    int numberOfRuns;
    cin >> numberOfRuns;
    for (int i = 0; i < numberOfRuns; i++) {
      prepareData();
      runMain();
    }
    return 0;
  }