ProgMe

Untitled

Dec 27th, 2020
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 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<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. int ans = 0;
  22. for(int i = 0; i < n; i++){
  23. s.insert(v[i].second);
  24. if(s.upper_bound(v[i].second) != s.end())
  25. ans += s.size() - s.order_of_key(*s.upper_bound(v[i].second));
  26. }
  27. cout << '\n';
  28. for(int i = 0; i < n; i++)
  29. swap(v[i].first, v[i].second);
  30. sort(v.begin(), v.end());
  31. s.clear();
  32. int ans_new = 0;
  33. for(int i = 0; i < n; i++){
  34. s.insert(v[i].second);
  35. if(s.upper_bound(v[i].second) != s.end())
  36. ans_new += s.size() - s.order_of_key(*s.upper_bound(v[i].second));
  37. }
  38. cout << min(ans, ans_new);
  39. }
Advertisement
Add Comment
Please, Sign In to add comment