Submission #989788

#TimeUsernameProblemLanguageResultExecution timeMemory
989788tch1cherinStar triangles (IZhO11_triangle)C++17
100 / 100
471 ms20428 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> X(N), Y(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }
  map<int, vector<int>> pos_x, pos_y;
  for (int i = 0; i < N; i++) {
    pos_x[X[i]].push_back(Y[i]);
    pos_y[Y[i]].push_back(X[i]);
  }
  long long answer = 0;
  for (int i = 0; i < N; i++) {
    int px = lower_bound(pos_x[X[i]].begin(), pos_x[X[i]].end(), Y[i]) - pos_x[X[i]].begin();
    int xs = (int)pos_x[X[i]].size();
    int py = lower_bound(pos_y[Y[i]].begin(), pos_y[Y[i]].end(), X[i]) - pos_y[Y[i]].begin();
    int ys = (int)pos_y[Y[i]].size();
    answer += 1LL * px * py + 1LL * px * (ys - 1 - py) + 1LL * (xs - 1 - px) * py + 1LL * (xs - 1 - px) * (ys - 1 - py);
  }
  cout << answer << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...