#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; }
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; } |