ProgMe

Untitled

Dec 27th, 2020
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h>
  3. #define int int64_t
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. template<typename T>
  9. using orset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10.  
  11. int32_t main() {
  12. ios::sync_with_stdio(false);
  13. cin.tie(nullptr); cout.tie(nullptr);
  14. int n;
  15. cin >> n;
  16. vector<pair<int, int>> v(n);
  17. for(auto &i: v)
  18. cin >> i.first >> i.second;
  19. sort(v.begin(), v.end());
  20. orset<int> s;
  21. multiset<int> tmp;
  22. int ans = 0;
  23. for(int i = 0; i < n; i++){
  24. s.insert(v[i].second);
  25. tmp.insert(v[i].second);
  26. if(s.upper_bound(v[i].second) != s.end())
  27. ans += s.size() - tmp.count(v[i].second) - s.order_of_key(*s.upper_bound(v[i].second));
  28. }
  29. cout << '\n';
  30. for(int i = 0; i < n; i++)
  31. swap(v[i].first, v[i].second);
  32. sort(v.begin(), v.end());
  33. s.clear();
  34. tmp.clear();
  35. int ans_new = 0;
  36. for(int i = 0; i < n; i++){
  37. s.insert(v[i].second);
  38. tmp.insert(v[i].second);
  39. if(s.upper_bound(v[i].second) != s.end())
  40. ans_new += s.size() - tmp.count(v[i].second) - s.order_of_key(*s.upper_bound(v[i].second));
  41. }
  42. cout << min(ans, ans_new);
  43. }
Advertisement
Add Comment
Please, Sign In to add comment