///MEMENTO MEMO, MEMENTO LONG LONG #include <bits/stdc++.h> #define DEBUG if(0) #define COUT cout << "\e[36m" #define ENDL "\e[39m" << endl #define VAR(v) " [\e[32m" << #v << "\e[36m=\e[91m" << v << "\e[36m] " using namespace std; typedef long long LL; struct Event { int pos,col,diff; }; ostream& operator<<(ostream& out, Event p) { out << "[" << p.pos << "," << p.col << (p.diff==1? "+" : "-") << "]"; return out; } inline bool comp(const Event& a, const Event& b) { return make_tuple(a.pos, a.col, a.diff) < make_tuple(b.pos, b.col, b.diff); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<Event> timeline(2*m); for (int i = 0; i < m; ++i) { int l, r, k; cin >> l >> r >> k; l--; k--; timeline[2*i] = {l, k, 1}; timeline[(2*i)+1] = {r, k, -1}; } sort(timeline.begin(), timeline.end(), comp); for(auto el : timeline) { DEBUG COUT << el << " "; } DEBUG COUT << ENDL; int j =0, ans = 0; int currColor[3] = {}; for (int i = 0; i < n; ++i) { for (; j < 2*m && timeline[j].pos <= i; ++j) { currColor[timeline[j].col]+= timeline[j].diff; } if(currColor[0] > 0 && currColor[1] > 0 && currColor[2] == 0) { DEBUG COUT << VAR(i) << VAR(j) << currColor[0] << " "<< currColor[1] << " " << currColor[2] << ENDL; ans++; } } cout << ans << "\n"; 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 | ///MEMENTO MEMO, MEMENTO LONG LONG #include <bits/stdc++.h> #define DEBUG if(0) #define COUT cout << "\e[36m" #define ENDL "\e[39m" << endl #define VAR(v) " [\e[32m" << #v << "\e[36m=\e[91m" << v << "\e[36m] " using namespace std; typedef long long LL; struct Event { int pos,col,diff; }; ostream& operator<<(ostream& out, Event p) { out << "[" << p.pos << "," << p.col << (p.diff==1? "+" : "-") << "]"; return out; } inline bool comp(const Event& a, const Event& b) { return make_tuple(a.pos, a.col, a.diff) < make_tuple(b.pos, b.col, b.diff); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<Event> timeline(2*m); for (int i = 0; i < m; ++i) { int l, r, k; cin >> l >> r >> k; l--; k--; timeline[2*i] = {l, k, 1}; timeline[(2*i)+1] = {r, k, -1}; } sort(timeline.begin(), timeline.end(), comp); for(auto el : timeline) { DEBUG COUT << el << " "; } DEBUG COUT << ENDL; int j =0, ans = 0; int currColor[3] = {}; for (int i = 0; i < n; ++i) { for (; j < 2*m && timeline[j].pos <= i; ++j) { currColor[timeline[j].col]+= timeline[j].diff; } if(currColor[0] > 0 && currColor[1] > 0 && currColor[2] == 0) { DEBUG COUT << VAR(i) << VAR(j) << currColor[0] << " "<< currColor[1] << " " << currColor[2] << ENDL; ans++; } } cout << ans << "\n"; return 0; } |