nested_ranges_check.cpp (1607B)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 using ui = unsigned int; 6 using l = long; 7 using ul = unsigned long; 8 using ll = long long; 9 using ull = unsigned long long; 10 11 using vi = vector<int>; 12 using vui = vector<ui>; 13 using vl = vector<l>; 14 using vul = vector<ul>; 15 using vll = vector<ll>; 16 using vull = vector<ull>; 17 18 void solve() 19 { 20 int n; 21 cin >> n; 22 vector< 23 pair< 24 pair<int, int>, 25 pair<int, int> 26 > 27 > a; 28 29 for (int i = 0; i < n; i++) { 30 int t, t2; 31 cin >> t >> t2; 32 a.push_back({{t, t2}, {i, 0}}); 33 } 34 35 sort(a.begin(), a.end(), 36 [](auto &l, auto &r) { 37 if (l.first.first == r.first.first) 38 return l.first.second < r.first.second; 39 return l.first.first > r.first.first; 40 }); 41 42 int mr = INT_MAX; 43 for (auto &x : a) { 44 if (mr <= x.first.second) 45 x.second.second = 1; 46 mr = min(mr, x.first.second); 47 } 48 sort(a.begin(), a.end(), 49 [](auto &l, auto &r) { 50 return l.second.first < r.second.first; 51 }); 52 53 for (auto x : a) { 54 cout << x.second.second << " "; 55 } 56 cout << "\n"; 57 58 sort(a.begin(), a.end(), 59 [](auto &l, auto &r) { 60 if (l.first.first == r.first.first) 61 return l.first.second > r.first.second; 62 return l.first.first < r.first.first; 63 }); 64 65 mr = 0; 66 for (auto &x : a) { 67 x.second.second = 0; 68 if (mr >= x.first.second) 69 x.second.second = 1; 70 mr = max(mr, x.first.second); 71 } 72 73 sort(a.begin(), a.end(), 74 [](auto &l, auto &r) { 75 return l.second.first < r.second.first; 76 }); 77 78 for (auto x : a) { 79 cout << x.second.second << " "; 80 } 81 cout << "\n"; 82 83 } 84 85 int main() 86 { 87 ios::sync_with_stdio(0); 88 cin.tie(0); 89 solve(); 90 }