Advertisement
danielvitor23

Gravatas Borboletas Estupendas

May 28th, 2022
1,813
333 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. using namespace __gnu_pbds;
  8.  
  9. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  10.  
  11. #define x first
  12. #define y second
  13.  
  14. int n;
  15. vector<pair<int, int>> v;
  16. map<int, ordered_set> mpx;
  17. map<int, ordered_set> mpy;
  18.  
  19. int main() {
  20.   cin.tie(0)->sync_with_stdio(0);
  21.  
  22.   cin >> n;
  23.  
  24.   for (int i = 0; i < n; ++i) {
  25.     int a, b;
  26.     cin >> a >>  b;
  27.     v.push_back({a, b});
  28.     mpx[a].insert(b);
  29.     mpy[b].insert(a);
  30.   }
  31.  
  32.   int64_t answer = 0;
  33.  
  34.   for (auto &p : v) {
  35.     int qtdAbaixo = mpx[p.x].order_of_key(p.y);
  36.     int qtdAcima = mpx[p.x].size() - 1 - qtdAbaixo;
  37.     int qtdEsquerda = mpy[p.y].order_of_key(p.x);
  38.     int qtdDireita = mpy[p.y].size() - 1 - qtdEsquerda;
  39.     answer += 2LL * qtdAbaixo * qtdDireita * qtdAcima * qtdEsquerda;
  40.   }
  41.  
  42.   cout << answer << '\n';
  43.  
  44. }
Advertisement
RAW Paste Data Copied
Advertisement