Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <bits/extc++.h>
- #define int int64_t
- using namespace std;
- using namespace __gnu_pbds;
- template<typename T>
- using orset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
- int32_t main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr); cout.tie(nullptr);
- int n;
- cin >> n;
- vector<pair<int, int>> v(n);
- for(auto &i: v)
- cin >> i.first >> i.second;
- sort(v.begin(), v.end());
- orset<int> s;
- multiset<int> tmp;
- int ans = 0;
- for(int i = 0; i < n; i++){
- s.insert(v[i].second);
- tmp.insert(v[i].second);
- if(s.upper_bound(v[i].second) != s.end())
- ans += s.size() - tmp.count(v[i].second) - s.order_of_key(*s.upper_bound(v[i].second));
- }
- cout << '\n';
- for(int i = 0; i < n; i++)
- swap(v[i].first, v[i].second);
- sort(v.begin(), v.end());
- s.clear();
- tmp.clear();
- int ans_new = 0;
- for(int i = 0; i < n; i++){
- s.insert(v[i].second);
- tmp.insert(v[i].second);
- if(s.upper_bound(v[i].second) != s.end())
- ans_new += s.size() - tmp.count(v[i].second) - s.order_of_key(*s.upper_bound(v[i].second));
- }
- cout << min(ans, ans_new);
- }
Advertisement
Add Comment
Please, Sign In to add comment