#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int maxn = 1000100; map<int,int> M; int types; int lookup(int p) { if (M.find(p) != M.end()) return M[p]; return M[p] = types++; } struct reser { int p; int a,b; int id; bool operator<(const reser &x) const { if (p != x.p) return p < x.p; if (b != x.b) return b > x.b; if (a != x.a) return a > x.a; return id < x.id; } }; int n,k; priority_queue<pii> qu[maxn]; priority_queue<pii> allres; vi ques; reser t[maxn]; int hour[maxn]; int main () { scanf("%d%d", &n, &k); FOR(i,n) { scanf("%d%d%d", &t[i].a, &t[i].b, &t[i].p); t[i].p = lookup(t[i].p); t[i].id=i; } sort(t,t+n); int lastp = -1; int curtime = -1; int it = 0; t[n].p=-2; while (it <= n) { if (t[it].p == lastp && t[it].b == curtime) { //printf("wrzucam [%d %d %d] do czasu %d\n", t[it].a, t[it].b, t[it].p, curtime); allres.push(mp(t[it].a, it)); it++; } else if (allres.empty()) { allres.push(mp(t[it].a, it)); //printf("wrzucam [%d %d %d] nowy czas to %d\n", t[it].a, t[it].b, t[it].p, t[it].b); curtime = t[it].b; lastp = t[it].p; it++; } else { pii cur = allres.top(); allres.pop(); //printf("wyciagam [%d %d %d] i ustawiam b=%d\n", t[cur.se].a, t[cur.se].b, t[cur.se].p, curtime); t[cur.se].b=curtime; if (t[cur.se].a > t[cur.se].b) { printf("NIE\n"); return 0; } curtime--; } } priority_queue<pair<int, pii> > events; FOR(i,n) { events.push(mp(-t[i].a, mp(1, i))); events.push(mp(-t[i].b, mp(-1, i))); } int res=0; while (!events.empty()) { pair<int, pii> cur = events.top(); int pos = cur.se.se; events.pop(); if (cur.se.fi == -1) { if (hour[t[pos].id] > 0) continue; int timer = -cur.fi; res++; //printf("timer = %d\n", timer); FOR(i,ques.size()) { pii reserv = qu[ques[i]].top(); qu[ques[i]].pop(); hour[t[reserv.se].id] = timer; if (qu[ques[i]].empty()) { ques[i]=ques.back(); ques.pop_back(); i--; } } } else { if (qu[t[pos].p].empty()) ques.pb(t[pos].p); qu[t[pos].p].push(mp(-t[pos].b, pos)); } } printf("%d\n", res); FOR(i,n) printf("%d\n", hour[i]); /* FOR(i,n) if (hour[t[i].id] < t[i].a || hour[t[i].id] > t[i].b) { printf("bledny czas na miejscu %d\n", t[i].id); } */ }
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 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int maxn = 1000100; map<int,int> M; int types; int lookup(int p) { if (M.find(p) != M.end()) return M[p]; return M[p] = types++; } struct reser { int p; int a,b; int id; bool operator<(const reser &x) const { if (p != x.p) return p < x.p; if (b != x.b) return b > x.b; if (a != x.a) return a > x.a; return id < x.id; } }; int n,k; priority_queue<pii> qu[maxn]; priority_queue<pii> allres; vi ques; reser t[maxn]; int hour[maxn]; int main () { scanf("%d%d", &n, &k); FOR(i,n) { scanf("%d%d%d", &t[i].a, &t[i].b, &t[i].p); t[i].p = lookup(t[i].p); t[i].id=i; } sort(t,t+n); int lastp = -1; int curtime = -1; int it = 0; t[n].p=-2; while (it <= n) { if (t[it].p == lastp && t[it].b == curtime) { //printf("wrzucam [%d %d %d] do czasu %d\n", t[it].a, t[it].b, t[it].p, curtime); allres.push(mp(t[it].a, it)); it++; } else if (allres.empty()) { allres.push(mp(t[it].a, it)); //printf("wrzucam [%d %d %d] nowy czas to %d\n", t[it].a, t[it].b, t[it].p, t[it].b); curtime = t[it].b; lastp = t[it].p; it++; } else { pii cur = allres.top(); allres.pop(); //printf("wyciagam [%d %d %d] i ustawiam b=%d\n", t[cur.se].a, t[cur.se].b, t[cur.se].p, curtime); t[cur.se].b=curtime; if (t[cur.se].a > t[cur.se].b) { printf("NIE\n"); return 0; } curtime--; } } priority_queue<pair<int, pii> > events; FOR(i,n) { events.push(mp(-t[i].a, mp(1, i))); events.push(mp(-t[i].b, mp(-1, i))); } int res=0; while (!events.empty()) { pair<int, pii> cur = events.top(); int pos = cur.se.se; events.pop(); if (cur.se.fi == -1) { if (hour[t[pos].id] > 0) continue; int timer = -cur.fi; res++; //printf("timer = %d\n", timer); FOR(i,ques.size()) { pii reserv = qu[ques[i]].top(); qu[ques[i]].pop(); hour[t[reserv.se].id] = timer; if (qu[ques[i]].empty()) { ques[i]=ques.back(); ques.pop_back(); i--; } } } else { if (qu[t[pos].p].empty()) ques.pb(t[pos].p); qu[t[pos].p].push(mp(-t[pos].b, pos)); } } printf("%d\n", res); FOR(i,n) printf("%d\n", hour[i]); /* FOR(i,n) if (hour[t[i].id] < t[i].a || hour[t[i].id] > t[i].b) { printf("bledny czas na miejscu %d\n", t[i].id); } */ } |