Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
#include <cstdio>
#include <algorithm>
#include <set>
#include <unordered_map>

using namespace std;

//#define DBG
//#define CHECK

#define TMAX 1000000001  // czas wi�kszy ni� wszystkie

int n, k;

struct Rezerw {
  int a, b, p;
  int maxt; // maksymalny czas na kt�ry mo�na j� zaplanowa�;
  int t;    // czas przydzielony
};
Rezerw *R;
int *ord; // porz�dek rezerwacji (aby nie sortowa� ca�ych struktur)

bool cmp_pb(int r1, int r2) {
  if (R[r1].p != R[r2].p)
    return R[r1].p < R[r2].p;
  else
    return R[r1].b > R[r2].b;
}

bool cmp_a(int r1, int r2) {return R[r1].a < R[r2].a;}

// ----------------------------------------------------------------------------------------------------

typedef pair<int, int> Para;
inline Para _Para(int a, int b) {return pair<int, int>(a, b);}

// miot�a
set<Para> M_maxt;      // (maxt, numer rezerwacji)
unordered_map<int, int> M_p;     // (przyrz�d, liczba wyst�pie�)
set<pair<Para, int> > P_maxt; // ((przyrz�d, maxt), numer rezerwacji)

#ifdef DBG
void dump(int i, int t)
{
  printf("i=%d, t=%d\n", i, t);
  printf(  "  M_maxt: ");
  for(Para p : M_maxt) printf("%d.%d ", p.second, p.first);
  printf("\n  M_p   : ");
  for(Para p : M_p) printf("%d.%d ", p.first, p.second);
  printf("\n  P_maxt: ");
  for(pair<Para, int> p : P_maxt) printf("%d.%d(%d) ", p.first.first, p.first.second, p.second);
  printf("\n");
}
#endif

// Zaplanowa� na t najwcze�niejsz� (w sensie maxt) rezerwacj� dla ka�dego przyrz�du na miotle.
void planuj(int t)
{
  vector<Para> todo; // (numer rezerwacji do zaplanowania, ile jest rezerwacji na ten przyrz�d)

  for(unordered_map<int, int>::iterator mp_it = M_p.begin(); mp_it != M_p.end(); ++mp_it) {
    // najwcze�niejsza w sensie maxt rezerwacja dla przyrz�du (musi by�)
    set<pair<Para, int> >::iterator pm_it = P_maxt.lower_bound(pair<Para, int>(Para(mp_it->first, -1), 0));
    todo.push_back(Para(pm_it->second, mp_it->second)); // numer rezerwacji, ile rezerwacji na dany przyrz�d
    #ifdef DBG
    //printf("   todo: %d %d\n", pm_it->second, mp_it->second);
    #endif // DBG
  }
  for (Para nr_ilep : todo) {
    Rezerw &rez = R[nr_ilep.first];
    rez.t = t; // planuj
    #ifdef CHECK
    if (t < rez.a || t > rez.b) {
      printf("CHECK 2!!! t=%d, rez=%d, (%d, %d..%d), maxt=%d\n", t, nr_ilep.first, rez.p, rez.a, rez.b, rez.maxt);
      exit(0);
    }
    #endif
    #ifdef DBG
    printf("    t=%d, rez=%d, (%d, %d..%d), maxt=%d\n", t, nr_ilep.first, rez.p, rez.a, rez.b, rez.maxt);
    #endif

    M_maxt.erase(Para(rez.maxt, nr_ilep.first)); // usu� z miot�y rezerwacj� (-maxt, nr rez)
    if (nr_ilep.second == 1)
      M_p.erase(rez.p); // nie ma ju� przyrz�du na miotle
    else
      M_p[rez.p] = nr_ilep.second - 1;
    P_maxt.erase(pair<Para, int>(_Para(rez.p, rez.maxt), nr_ilep.first)); // usu� z miot�y ((przyrz�d, maxt), nr rez)
  }
}

int licz()
{
  /*
      Dla ka�dej rezerwacji ustali� najp�niejszy mo�liwy czas:
          Posortowa� je wg przyrz�du i czasu ko�ca malej�co.
          Przej�� kolejno i wrzuca� do zbioru uporz�dkowanego wg czasu pocz�tku.
          maxt trzeba ustawia� najpierw dla tych o najp�niejszym pocz�tku.
      Posortowa� wg czasu pocz�tku.
      Bierzemy kolejne id�c po czasach pocz�tku.
          Struktura danych (miot�a, t - czas)
              Zawiera rezerwacje, kt�re w�a�nie chcemy zaplanowa�. Mo�e by� to wi�cej ni� jedna dla przyrz�du.
              Musimy zna� maximum z maxt dla wszystkich rezerwacji na miotle
                  M_maxt set<int, int> zawieraj�cy (-maxt, numer rez) - aby �atwiej przez begin() bra� max
              Musimy zna� przyrz�dy na miotle oraz liczb� rezerwacji na przyrz�d
                  M_p    map<int, int> dla przyrz�d�w (przyrz�d, liczba wyst�pie�)
              Dla ka�dego przyrz�du musimy zna� tak� o najwcze�niejszym maxt i najp�niejszym maxt
                  P_maxt set<<int, int>, int> zawieraj�cy ((przyrz�d, maxt), numer rezerwacji)
                  najwcze�niejsze maxt dla p: lower_bound(p, -1)
                  najp�niejsze maxt dla p: upper_bound(p, TMAX) - 1
              Niezmiennik na miotle:
                Wszystkie na miotle mo�na zaplanowa� na t
                Nie mo�e by� takiej rezerwacji dla kt�rej maxt > t (bo ju� za p�no)
                Nie mo�e by� za du�o dla jednego przyrz�du tzn. t + M_p[p] > max(maxt) dla p (bo nie zd��ymy ich zaplanowa�)
          Je�li kolejna rezerwacja ma a > t to:
            Je�li si� oka�e, �e a > min(maxt) z rezerwacji z miot�y to:
                Trzeba zaplanowa� na t najwcze�niejsz� (w sensie maxt) rezerwacj� dla ka�dego przyrz�du na miotle.
            ustawiamy t := a
          Po do�o�eniu nowej rezerwacji na p trzeba sprawdzi� czy za du�o si� nie zgromadzi�o na ten przyrz�d.
          Je�li t + M_p[p] > max(maxt) z rezerwacji dla przyrz�du na miotle to nie zd��ymy ich zrobi� p�niej ni� teraz:
              Trzeba zaplanowa� na t najwcze�niejsz� (w sensie maxt) rezerwacj� dla ka�dego przyrz�du na miotle.
      Je�li nie ma ju� wi�cej to trzeba zaplanowa� wszystkie z miot�y na kolejne t, t+1, ... dop�ki co� jest na miotle.
  */
  int i, t;
  int wyn = 0;

  sort(ord, ord + n, cmp_pb); // sortowanie wg przyrz�du i czasu b malej�co

  i = 0;  // numer kolejny rezerwacji w porz�dku ord
  while (i < n) { // dla ka�dego przyrz�du
    set<Para> PQ;  // rezerwacje o b >= t (-b, numer rez)  - aby �atwo wyci�ga� najwi�ksze
    set<Para> PQ2; // rezerwacje o b >= maxt (-a, numer rez)  - aby �atwo wyci�ga� najwi�ksze
    int maxt = TMAX;      // max czas jaki mo�na jeszcze przydzieli�
    int p = R[ord[i]].p;    // aktualny przyrz�d
    while (i < n && R[ord[i]].p == p) {  // rezerwacje na dany przyrz�d
      #ifdef CHECK
      if (n < 100 || i % (n / 100) == 0) printf("%d%%\n", 100 * i / n);
      #endif // CHECK
      t = R[ord[i]].b; // czas ko�cowy rezerwacji
      while (i < n && R[ord[i]].p == p && R[ord[i]].b == t) { // do PQ wszystkie rezerwacje na ten przyrz�d z czasem ko�ca b
        PQ.insert(Para(-R[ord[i]].b, ord[i]));
        #ifdef DBG
        printf("PQ.insert(%d, %d)\n", -R[ord[i]].b, ord[i]);
        #endif // DBG
        i++;
      }
      if (PQ2.size() == 0) {
        maxt = min(maxt, -PQ.begin()->first); // cofamy maxt je�li rezerwacja o najp�niejszym b ma b < maxt
        #ifdef DBG
        printf("t=%d, maxt=%d, PQ.max=%d\n", t, maxt, -PQ.begin()->first);
        #endif // DBG
        while (true) {
          set<Para>::iterator it = PQ.begin();
          if (-it->first < maxt)
            break;
          else {
            int nr = PQ.begin()->second;
            PQ2.insert(Para(-R[nr].a, nr));
            PQ.erase(it);
          }
        }
      }
      bool ostatnia = (i == n || R[ord[i]].p != p); // wszystkie dla przyrz�du ju� mamy
      // mo�na bezpiecznie przydzieli� do czasu t (brak konfliktu z rezerwacjami kt�rych nie ma w PQ) lub wszystkie jak nie ma innych dla p
      while (PQ2.size() && (maxt >= t || ostatnia)) {
        set<Para>::iterator it = PQ2.begin();  // najpierw te o najwi�kszym a
        Rezerw &rez = R[it->second];
        rez.maxt = maxt--;
        if (rez.a > rez.maxt) return -1;    // nie da si� zaplanowa� bo kolejna chce si� zaczyna� p�niej ni� maxt dla poprzedniej
        #ifdef DBG
        printf("rez=%d, (%d, %d..%d), maxt=%d t=%d\n", it->second, p, rez.a, rez.b, rez.maxt, t);
        #endif // DBG
        #ifdef CHECK
        if (rez.maxt < rez.a || rez.maxt > rez.b) {
          printf("CHECK 1!!! t=%d, rez=%d, (%d, %d..%d), maxt=%d\n", t, it->second, rez.p, rez.a, rez.b, rez.maxt);
          exit(0);
        }
        #endif
        PQ2.erase(it);
        while (PQ.size()) {  // sprawdzi� co mo�na przerzuci� z PQ po zmniejszeniu maxt
          set<Para>::iterator it = PQ.begin();
          if (-it->first < maxt)
            break;
          else {
            int nr = PQ.begin()->second;
            PQ2.insert(Para(-R[nr].a, nr));
            PQ.erase(it);
          }
        }
      }
    }
  }

  #if defined DBG || defined CHECK
  printf("faza 2\n");
  #endif
  sort(ord, ord + n, cmp_a); // sortowanie wg czasu a rosn�co

  t = 0; // ostatni zaplanowany czas
  for (i = 0; i < n; ++i) {
    #ifdef CHECK
    if (n < 100 || i % (n / 100) == 0) printf("%d%%\n", 100 * i / n);
    #endif // CHECK
    int nr = ord[i]; // numer rezerwacji
    Rezerw &rez = R[nr];
    #ifdef DBG
    printf("rez=%d, (%d, %d..%d), maxt=%d\n", nr, rez.p, rez.a, rez.b, rez.maxt);
    dump(i, t);
    #endif // DBG
    if (rez.a > t) { // nie nast�pi dla t = 0 (pierwszy obr�t)
      while (M_maxt.size() > 0 && rez.a > M_maxt.begin()->first) {
        #ifdef DBG
        printf("  planuj A (%d > %d)\n", rez.a, M_maxt.begin()->first);
        #endif // DBG
        planuj(t);
        wyn++;
      }
      t = rez.a;
    }
    // TODO: a mo�e tu przyspieszy jak dodamy od razu wszystkie rezerwacje dla danego a?

    // dok�adamy rezerwacj� do miot�y
    M_maxt.insert(_Para(rez.maxt, nr));

    int ile_dla_p; // ile na miotle jest rezerwacji dla przyrz�du
    unordered_map<int, int>::iterator mp_it = M_p.find(rez.p);
    if (mp_it == M_p.end())
      ile_dla_p = M_p[rez.p] = 1;
    else
      ile_dla_p = M_p[rez.p] = mp_it->second + 1;

    // dok�adamy informacj� o maxt dla przyrz�du
    P_maxt.insert(pair<Para, int>(_Para(rez.p, rez.maxt), nr));
    set<pair<Para, int> >::iterator pm_it = P_maxt.upper_bound(pair<Para, int>(_Para(rez.p, TMAX), 0));
    pm_it--; // cofni�cie na ostatni

    #ifdef DBG
    dump(i, t);
    #endif // DBG

    if (t + ile_dla_p > pm_it->first.second) {
      // czas + liczba rezerwacji dla do�o�onego przyrz�du > maxt dla rezerwacji na ten przyrz�d
      #ifdef DBG
      printf("  planuj B (%d + %d > %d)\n", t, ile_dla_p, pm_it->first.second);
      #endif // DBG
      planuj(t++);
      wyn++;
    }
      // TODO: czy na pewno wystarczy raz? chyba tak bo dla ka�dego przyrz�du si� zaplanuje
  }
  while (M_maxt.size()) {
    #ifdef DBG
    printf("  planuj C\n");
    #endif // DBG
    planuj(t++);
    wyn++;
  }

  return wyn;
}

// ----------------------------------------------------------------------------------------------------

int czytaj()
{
  int i;
  scanf("%d%d", &n, &k);
  R = new Rezerw[n];
  ord = new int[n];
  for (i = 0; i < n; ++i) {
    ord[i] = i;
    scanf("%d%d%d", &R[i].a, &R[i].b, &R[i].p);
  }
}

// ----------------------------------------------------------------------------------------------------

int main()
{
  czytaj();
  #ifdef CHECK
  printf("wczytane\n");
  #endif // CHECK
  int wyn = licz();
  if (wyn == -1)
    printf("NIE\n");
  else {
    printf("%d\n", wyn);
    #ifndef CHECK
    for (int i = 0; i < n; ++i) printf("%d\n", R[i].t);
    #endif // CHECK
  }
  return 0;
}