Submission #935112

#	Time	Username	Problem	Language	Result	Execution time	Memory
935112		ind1v	Star triangles (IZhO11_triangle)	C++11	100 / 100	220 ms	14400 KiB

triangle

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int n;
int x[N], y[N];
int cx[N], cy[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
  }
  vector<int> vx;
  copy(x + 1, x + n + 1, back_inserter(vx));
  sort(vx.begin(), vx.end());
  vx.erase(unique(vx.begin(), vx.end()), vx.end());
  vector<int> vy;
  copy(y + 1, y + n + 1, back_inserter(vy));
  sort(vy.begin(), vy.end());
  vy.erase(unique(vy.begin(), vy.end()), vy.end());
  for (int i = 1; i <= n; i++) {
    cx[lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin()]++;
    cy[lower_bound(vy.begin(), vy.end(), y[i]) - vy.begin()]++;
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += (cx[lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin()] - 1) * (cy[lower_bound(vy.begin(), vy.end(), y[i]) - vy.begin()] - 1);
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 100 / 100