#include <iostream> #include <vector> #include <set> #include <string> #include <utility> #include <algorithm> using namespace std; void fix(vector<pair<int, int>> &A, vector<pair<int, int>> &ans) { if (A.size() == 0) return; pair<int, int> p1 = A[0]; for (auto p2 : A) { if (p1.second < p2.first) { ans.push_back({p1.first, p1.second}); p1.first = p2.first; p1.second = p2.second; } else { p1.second = max(p1.second, p2.second); } } ans.push_back({p1.first, p1.second}); } int main() { int n, m; cin >> n >> m; vector<pair<int, int>> Z; vector<pair<int, int>> N; vector<pair<int, int>> C; for (int i = 0; i < m; i++) { int l, r, k; cin >> l >> r >> k; if (k == 1) { Z.push_back(make_pair(l, r)); } else if (k == 2) { N.push_back(make_pair(l, r)); } else { C.push_back(make_pair(l, r)); } } sort(Z.begin(), Z.end()); sort(N.begin(), N.end()); sort(C.begin(), C.end()); vector<pair<int, int>> Zs; vector<pair<int, int>> Ns; vector<pair<int, int>> Cs; fix(Z, Zs); fix(N, Ns); fix(C, Cs); int count = 0; vector<int> ans(n + 2, 0); for (auto p : Zs) { for (int i = p.first; i <= p.second; i++) { ans[i] = 1; } } for (auto p : Ns) { for (int i = p.first; i <= p.second; i++) { if (ans[i] >= 1) { ans[i]++; } if (ans[i] == 2) { count++; } } } for (auto p : Cs) { for (int i = p.first; i <= p.second; i++) { if (ans[i] == 2) { count--; } } } cout << count << 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 | #include <iostream> #include <vector> #include <set> #include <string> #include <utility> #include <algorithm> using namespace std; void fix(vector<pair<int, int>> &A, vector<pair<int, int>> &ans) { if (A.size() == 0) return; pair<int, int> p1 = A[0]; for (auto p2 : A) { if (p1.second < p2.first) { ans.push_back({p1.first, p1.second}); p1.first = p2.first; p1.second = p2.second; } else { p1.second = max(p1.second, p2.second); } } ans.push_back({p1.first, p1.second}); } int main() { int n, m; cin >> n >> m; vector<pair<int, int>> Z; vector<pair<int, int>> N; vector<pair<int, int>> C; for (int i = 0; i < m; i++) { int l, r, k; cin >> l >> r >> k; if (k == 1) { Z.push_back(make_pair(l, r)); } else if (k == 2) { N.push_back(make_pair(l, r)); } else { C.push_back(make_pair(l, r)); } } sort(Z.begin(), Z.end()); sort(N.begin(), N.end()); sort(C.begin(), C.end()); vector<pair<int, int>> Zs; vector<pair<int, int>> Ns; vector<pair<int, int>> Cs; fix(Z, Zs); fix(N, Ns); fix(C, Cs); int count = 0; vector<int> ans(n + 2, 0); for (auto p : Zs) { for (int i = p.first; i <= p.second; i++) { ans[i] = 1; } } for (auto p : Ns) { for (int i = p.first; i <= p.second; i++) { if (ans[i] >= 1) { ans[i]++; } if (ans[i] == 2) { count++; } } } for (auto p : Cs) { for (int i = p.first; i <= p.second; i++) { if (ans[i] == 2) { count--; } } } cout << count << endl; return 0; } |