Advertisement
YEZAELP

SMMR-063: Watch Men

Apr 9th, 2021
164
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. using pll = pair <lli, lli>;
  6. const int N = 2e5;
  7. const lli INF = 2e18;
  8.  
  9. int main(){
  10.  
  11.  
  12.     int n;
  13.     lli ans = 0;
  14.     scanf("%d", &n);
  15.  
  16.     map <lli, int> same;
  17.     vector <pll> point1, point2;
  18.     for(int i=1;i<=n;i++){
  19.         lli x, y;
  20.         scanf("%lld%lld", &x, &y);
  21.         same[y] ++;
  22.         point1.push_back({x, y});
  23.         point2.push_back({y, x});
  24.     }
  25.  
  26.     sort(point1.begin(), point1.end());
  27.     sort(point2.begin(), point2.end());
  28.  
  29.     lli prev = -INF;
  30.     lli cnt = 0;
  31.     for(auto p: point1){
  32.         lli x, y;
  33.         x = p.first;
  34.         y = p.second;
  35.         if(prev == -INF){
  36.             prev = x;
  37.             cnt = 1;
  38.             continue;
  39.         }
  40.         if(prev == x){
  41.             cnt ++;
  42.         }
  43.         else {
  44.             if(cnt > 1) ans += (lli)(cnt)*(cnt-1) / 2;
  45.             prev = x;
  46.             cnt = 1;
  47.         }
  48.     }
  49.     if(cnt > 1) ans += (lli)(cnt)*(cnt-1) / 2;
  50.  
  51.     lli prey = -INF, prex = -INF;
  52.     cnt = 0;
  53.     lli h = 1;
  54.     vector <lli> X;
  55.     for(auto p: point2){
  56.         lli x, y;
  57.         y = p.first;
  58.         x = p.second;
  59.         if(prey == -INF){
  60.             prey = y;
  61.             prex = x;
  62.             cnt = 1;
  63.             continue;
  64.         }
  65.         if(prey == y){
  66.             if(prex == x) cnt ++;
  67.             else {
  68.                 X.push_back(cnt);
  69.                 cnt = 1;
  70.             }
  71.         }
  72.         else {
  73.             X.push_back(cnt);
  74.             int sz = X.size();
  75.             for(int i=0;i<sz-1;i++){
  76.                 for(int j=i+1;j<sz;j++){
  77.                     ans += (lli) X[i]*X[j];
  78.                 }
  79.             }
  80.             if(sz != 0) X.clear();
  81.             cnt = 1;
  82.         }
  83.         prex = x;
  84.         prey = y;
  85.     }
  86.  
  87.     X.push_back(cnt);
  88.     int sz = X.size();
  89.     for(int i=0;i<sz-1;i++){
  90.         for(int j=i+1;j<sz;j++){
  91.             ans += (lli) X[i]*X[j];
  92.         }
  93.     }
  94.  
  95.     printf("%lld", ans);
  96.  
  97.     return 0;
  98. }
  99. /**
  100.  
  101. 4
  102. 1 2
  103. 1 2
  104. 1 3
  105. 4 2
  106.  
  107. 3
  108. 1 1
  109. 7 5
  110. 1 5
  111.  
  112. 6
  113. 0 0
  114. 0 1
  115. 0 2
  116. -1 1
  117. 0 1
  118. 1 1
  119.  
  120. 7
  121. 1 2
  122. 1 2
  123. 1 2
  124. 1 3
  125. 1 3
  126. 4 2
  127. 4 2
  128.  
  129. **/
  130.  
Advertisement
RAW Paste Data Copied
Advertisement