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
#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>

using namespace std;

typedef pair<long, long> interval;

struct reserv {
	long p;
	int num;
	interval inter;
};

bool res_comp(pair<long, reserv> res1, pair<long, reserv> res2) {
	return (res1.second.inter.first < res2.second.inter.first);
}

void assign_time(map<long, reserv>& act_use, vector<long>& res_times, long date) {
	for (map<long, reserv>::const_iterator it = act_use.begin();
		it != act_use.end(); it++) {
		res_times[it->second.num] = date;
	}
}

int main() {
	int n, timecount;
	long k, a, b, p;
	map<long, reserv> act_use;
	interval act_inter;
	map<long, reserv>::iterator it;
	vector<pair<long, reserv> > res;
	vector<long> res_times;

	cin >> n >> k;
	res.resize(n);
	res_times.resize(n);
	for (int i = 0; i != n; i++) {
		res[i].second.num = i;
		cin >> res[i].second.inter.first >> res[i].second.inter.second >> res[i].first;
	}
	sort(res.begin(), res.end(), res_comp);

	act_inter = res[0].second.inter;
	act_use.insert(res[0]);
	timecount = 0;
	for (int i = 1; i != n; i++) {
		long min_common_date = act_inter.first;
		it = act_use.find(res[i].first);
		if (it == act_use.end()) {
			if (act_inter.second < res[i].second.inter.first) {
				timecount++;
				assign_time(act_use, res_times, min_common_date);
				act_use.clear();
				act_inter = res[i].second.inter;
			}
			else {
				act_inter.first = max(act_inter.first, res[i].second.inter.first);
				act_inter.second = min(act_inter.second, res[i].second.inter.second);
			}
			act_use.insert(res[i]);
		}
		else {
			if (res[i].second.inter.second > it->second.inter.second) {
				timecount++;
				assign_time(act_use, res_times, min_common_date);
				act_use.clear();
				res[i].second.inter.first = 
				max(res[i].second.inter.first, min_common_date+1);
				act_use.insert(res[i]);
				act_inter = res[i].second.inter;
			}
			else {
				if (act_inter.second >= res[i].second.inter.first) {
					timecount++;
					assign_time(act_use, res_times, res[i].second.inter.first);
					res_times[res[i].second.num] = res[i].second.inter.first;
					res_times[it->second.num] = 0;
					//it->second.inter.first = res[i].second.inter.first+1;
					act_use.clear();
					act_use.insert(*it);
					act_inter = it->second.inter;
				}
				else {
					timecount++;
					res_times[res[i].second.num] = res[i].second.inter.first;
				}
			}
			if (it->second.inter.first > it->second.inter.second ||
				res[i].second.inter.first > res[i].second.inter.second)
			{
				cout << "NIE" << endl;
				return 0;
			}	
		}
	}
	if (!act_use.empty()) {
		assign_time(act_use, res_times, act_inter.first);
	}

	cout << timecount << endl;
	for (int i = 0; i != n; i++)
		cout << res_times[i] << endl;
	return 0;
}