Submission #585446

#	Time	Username	Problem	Language	Result	Execution time	Memory
585446		Shin	Star triangles (IZhO11_triangle)	C++14	100 / 100	367 ms	53972 KiB

triangle

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 6e5 + 7;
int n;
int x[N];
int y[N];
pair<int, int> a[N];
map<int, int> cnt[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  vector<int> val;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i].fi >> a[i].se;
    val.push_back(a[i].fi);
    val.push_back(a[i].se);
  }
  sort(all(val));
  val.erase(unique(all(val)), val.end());
  for (int i = 1; i <= n; i ++) {
    a[i].fi = lower_bound(all(val), a[i].fi) - val.begin();
    a[i].se = lower_bound(all(val), a[i].se) - val.begin();
    x[a[i].fi] ++;
    y[a[i].se] ++;
    cnt[a[i].fi][a[i].se] ++;
  }
  long long res = 0;
  for (int i = 1; i <= n; i ++) {
    int hors = x[a[i].fi] - cnt[a[i].fi][a[i].se];
    int vers = y[a[i].se] - cnt[a[i].fi][a[i].se];
    res += 1LL * cnt[a[i].fi][a[i].se] * hors * vers;
  }
  cout << res;
  return 0;
}

• Subtask 1: 100 / 100