#include <cstdio> #include <queue> #include <algorithm> #include <vector> using namespace std; const int N = 1000001; int pos[N]; int a[N]; int b[N]; int p[N]; bool u[N]; priority_queue<pair<int, int>> gq; priority_queue<pair<int, int>> q[N]; vector<int> vec[N]; int ptr1[N]; int ptr2[N]; int timee[N]; const int inf = 1000000001; int main() { int n, k; scanf("%d %d", &n, &k); vector<int> vecp; for(int i = 0; i < n; i++) { scanf("%d %d %d", a + i, b + i, p + i); vecp.push_back(p[i]); } sort(vecp.begin(), vecp.end()); for(int i = 0; i < n; i++) { p[i] = lower_bound(vecp.begin(), vecp.end(), p[i]) - vecp.begin(); vec[p[i]].push_back(i); } vector<pair<int, int>> vp; for(int i = 0; i < n; i++) { sort(vec[i].begin(), vec[i].end(), [](int A, int B) { return b[A] > b[B]; }); priority_queue<pair<int, int>> pq; int p = inf; for(int j = 0; j < vec[i].size(); j++) { int k = vec[i][j]; pq.push(make_pair(a[k], k)); p = min(p, b[k]); while(!pq.empty() && (j + 1 == vec[i].size() || b[vec[i][j+1]] < p)) { if(p < pq.top().first) { puts("NIE"); return 0; } // printf("%d ", pq.top().second); pos[pq.top().second] = p--; pq.pop(); } } sort(vec[i].begin(), vec[i].end(), [](int A, int B) { return a[A] < a[B]; }); } // for(int i = 0; i < n; i++) // printf("pos[%d] = %d\n", i, pos[i]); for(int i = 0; i < n; i++) vp.push_back(make_pair(pos[i], i)); sort(vp.begin(), vp.end()); for(int i = 0; i < n; i++) { if(!vec[i].empty()) gq.push(make_pair(-a[vec[i][0]], i)); } int ans = 0; for(int i = 0; i < n; i++) { if(u[vp[i].second]) continue; ans++; int k = vp[i].first; vector<int> v; while(!gq.empty() && -gq.top().first <= k) { int l = gq.top().second; gq.pop(); while(ptr1[l] < vec[l].size() && a[vec[l][ptr1[l]]] <= k) { q[l].push(make_pair(-pos[vec[l][ptr1[l]]], vec[l][ptr1[l]])); ptr1[l]++; } if(q[l].empty()) continue; int best = q[l].top().second; // if(k == pos[best]) // { q[l].pop(); u[best] = true; timee[best] = k; while(ptr2[l] < vec[l].size() && u[vec[l][ptr2[l]]]) ptr2[l]++; // } v.push_back(l); } // printf("a\n"); for(int l: v) { // printf("%d\n", l); if(ptr2[l] < vec[l].size()) { // if(ptr2[l] < 0 || ptr2[l] >= vec[l].size() || vec[l][ptr2[l]] < 0 || vec[l][ptr2[l]] >= n) // printf("%d\n", vec[l].size()); auto p = make_pair(-a[vec[l][ptr2[l]]], l); gq.push(p); } } // printf("b\n"); } printf("%d\n", ans); for(int i = 0; i < n; i++) printf("%d\n", timee[i]); }
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 | #include <cstdio> #include <queue> #include <algorithm> #include <vector> using namespace std; const int N = 1000001; int pos[N]; int a[N]; int b[N]; int p[N]; bool u[N]; priority_queue<pair<int, int>> gq; priority_queue<pair<int, int>> q[N]; vector<int> vec[N]; int ptr1[N]; int ptr2[N]; int timee[N]; const int inf = 1000000001; int main() { int n, k; scanf("%d %d", &n, &k); vector<int> vecp; for(int i = 0; i < n; i++) { scanf("%d %d %d", a + i, b + i, p + i); vecp.push_back(p[i]); } sort(vecp.begin(), vecp.end()); for(int i = 0; i < n; i++) { p[i] = lower_bound(vecp.begin(), vecp.end(), p[i]) - vecp.begin(); vec[p[i]].push_back(i); } vector<pair<int, int>> vp; for(int i = 0; i < n; i++) { sort(vec[i].begin(), vec[i].end(), [](int A, int B) { return b[A] > b[B]; }); priority_queue<pair<int, int>> pq; int p = inf; for(int j = 0; j < vec[i].size(); j++) { int k = vec[i][j]; pq.push(make_pair(a[k], k)); p = min(p, b[k]); while(!pq.empty() && (j + 1 == vec[i].size() || b[vec[i][j+1]] < p)) { if(p < pq.top().first) { puts("NIE"); return 0; } // printf("%d ", pq.top().second); pos[pq.top().second] = p--; pq.pop(); } } sort(vec[i].begin(), vec[i].end(), [](int A, int B) { return a[A] < a[B]; }); } // for(int i = 0; i < n; i++) // printf("pos[%d] = %d\n", i, pos[i]); for(int i = 0; i < n; i++) vp.push_back(make_pair(pos[i], i)); sort(vp.begin(), vp.end()); for(int i = 0; i < n; i++) { if(!vec[i].empty()) gq.push(make_pair(-a[vec[i][0]], i)); } int ans = 0; for(int i = 0; i < n; i++) { if(u[vp[i].second]) continue; ans++; int k = vp[i].first; vector<int> v; while(!gq.empty() && -gq.top().first <= k) { int l = gq.top().second; gq.pop(); while(ptr1[l] < vec[l].size() && a[vec[l][ptr1[l]]] <= k) { q[l].push(make_pair(-pos[vec[l][ptr1[l]]], vec[l][ptr1[l]])); ptr1[l]++; } if(q[l].empty()) continue; int best = q[l].top().second; // if(k == pos[best]) // { q[l].pop(); u[best] = true; timee[best] = k; while(ptr2[l] < vec[l].size() && u[vec[l][ptr2[l]]]) ptr2[l]++; // } v.push_back(l); } // printf("a\n"); for(int l: v) { // printf("%d\n", l); if(ptr2[l] < vec[l].size()) { // if(ptr2[l] < 0 || ptr2[l] >= vec[l].size() || vec[l][ptr2[l]] < 0 || vec[l][ptr2[l]] >= n) // printf("%d\n", vec[l].size()); auto p = make_pair(-a[vec[l][ptr2[l]]], l); gq.push(p); } } // printf("b\n"); } printf("%d\n", ans); for(int i = 0; i < n; i++) printf("%d\n", timee[i]); } |