#include <iostream> #include <queue> using namespace std; class Delivery { public: int i; char r; int w; int t; Delivery(int ii, char rr, int ww, int tt) : i(ii), r(rr), w(ww), t(tt) {} }; class Item { public: int x; Item *next; int count; Item(int xx, Item *n, int c) : x(xx), next(n), count(c) {} }; class QueueItem { public: long long count; int del; QueueItem(long long c, int d) : count(c), del(d) {} bool operator<(const QueueItem &qi) const { return count < qi.count; } }; Item *seq[2][2000001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, r, w, t; cin >> n; Delivery *devs[2][n]; long long allCrashes = 0; long long crashes[n]; for (int i = 0; i < n; i++) { crashes[i] = 0; } Item *items[n]; for (int i = 0; i < n; i++) { items[i] = 0; } priority_queue<QueueItem> pq; int nn[2] = {0, 0}; for (int i = 0; i < n; i++) { cin >> r >> w >> t; r--; devs[r][nn[r]] = new Delivery(i, (char) r, w, t); nn[r]++; } for (int k = 0; k < 2; k++) { for (int i = 0; i < nn[k]; i++) { int seqNo = devs[k][i]->t - devs[k][i]->w + 1000000; Item *item = new Item(devs[k][i]->i, seq[k][seqNo], seq[k][seqNo] == 0 ? 1 : seq[k][seqNo]->count + 1); seq[k][seqNo] = item; } } for (int k = 0; k < 2; k++) { for (int i = 0; i < nn[k]; i++) { int seqNo = devs[k][i]->t - devs[k][i]->w + 1000000; items[devs[k][i]->i] = seq[1-k][seqNo]; if(seq[1-k][seqNo] != 0) { allCrashes += seq[1 - k][seqNo]->count; crashes[devs[k][i]->i] += seq[1 - k][seqNo]->count; } } } allCrashes /= 2; for (int i = 0; i < n; i++) { pq.push(QueueItem(crashes[i], i)); } int result = 0; while (allCrashes > 0 && !pq.empty()) { QueueItem item = pq.top(); pq.pop(); int i = item.del; if (item.count != crashes[i]) { pq.push(QueueItem(crashes[i], i)); } else { Item *item = items[i]; while (item != 0) { int j = item->x; if (crashes[j] > 0) { crashes[j]--; crashes[i]--; allCrashes--; } item = item->next; } result++; } } cout << result << 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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <iostream> #include <queue> using namespace std; class Delivery { public: int i; char r; int w; int t; Delivery(int ii, char rr, int ww, int tt) : i(ii), r(rr), w(ww), t(tt) {} }; class Item { public: int x; Item *next; int count; Item(int xx, Item *n, int c) : x(xx), next(n), count(c) {} }; class QueueItem { public: long long count; int del; QueueItem(long long c, int d) : count(c), del(d) {} bool operator<(const QueueItem &qi) const { return count < qi.count; } }; Item *seq[2][2000001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, r, w, t; cin >> n; Delivery *devs[2][n]; long long allCrashes = 0; long long crashes[n]; for (int i = 0; i < n; i++) { crashes[i] = 0; } Item *items[n]; for (int i = 0; i < n; i++) { items[i] = 0; } priority_queue<QueueItem> pq; int nn[2] = {0, 0}; for (int i = 0; i < n; i++) { cin >> r >> w >> t; r--; devs[r][nn[r]] = new Delivery(i, (char) r, w, t); nn[r]++; } for (int k = 0; k < 2; k++) { for (int i = 0; i < nn[k]; i++) { int seqNo = devs[k][i]->t - devs[k][i]->w + 1000000; Item *item = new Item(devs[k][i]->i, seq[k][seqNo], seq[k][seqNo] == 0 ? 1 : seq[k][seqNo]->count + 1); seq[k][seqNo] = item; } } for (int k = 0; k < 2; k++) { for (int i = 0; i < nn[k]; i++) { int seqNo = devs[k][i]->t - devs[k][i]->w + 1000000; items[devs[k][i]->i] = seq[1-k][seqNo]; if(seq[1-k][seqNo] != 0) { allCrashes += seq[1 - k][seqNo]->count; crashes[devs[k][i]->i] += seq[1 - k][seqNo]->count; } } } allCrashes /= 2; for (int i = 0; i < n; i++) { pq.push(QueueItem(crashes[i], i)); } int result = 0; while (allCrashes > 0 && !pq.empty()) { QueueItem item = pq.top(); pq.pop(); int i = item.del; if (item.count != crashes[i]) { pq.push(QueueItem(crashes[i], i)); } else { Item *item = items[i]; while (item != 0) { int j = item->x; if (crashes[j] > 0) { crashes[j]--; crashes[i]--; allCrashes--; } item = item->next; } result++; } } cout << result << endl; return 0; } |