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