Submission #989788

#	Time	Username	Problem	Language	Result	Execution time	Memory
989788		tch1cherin	별들과 삼각형 (IZhO11_triangle)	C++17	100 / 100	471 ms	20428 KiB

triangle

#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";
}

• Subtask 1: 100 / 100