제출 #1219523

#제출 시각아이디문제언어결과실행 시간메모리
1219523lukasuliashvili별들과 삼각형 (IZhO11_triangle)C++20
100 / 100
460 ms12400 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N = 300005;

int x[N], y[N];
vector<int> vecx, vecy;
map<int, int> comp; 
int cntX[N], cntY[N];

signed main() {

    int n;
    cin >> n;
    rep(i, 1, n) {
        int u, v;
        cin >> u >> v;
        x[i] = u;
        y[i] = v;
        vecx.pb(u);
        vecy.pb(v);
    }

    
    int idx = 1;
    sort(vecx.begin(), vecx.end());
    for (int i = 0; i < vecx.size(); i++) {
        if (comp.count(vecx[i]) == 0)
            comp[vecx[i]] = idx++;
    }
    sort(vecy.begin(), vecy.end());
    for (int i = 0; i < vecy.size(); i++) {
        if (comp.count(vecy[i]) == 0)
            comp[vecy[i]] = idx++;
    }

    
    rep(i, 1, n) {
        int cx = comp[x[i]];
        int cy = comp[y[i]];
        cntX[cx]++;
        cntY[cy]++;
    }

   
    int ans = 0;
    rep(i, 1, n) {
        int cx = comp[x[i]];
        int cy = comp[y[i]];
        ans += (cntX[cx] - 1) * (cntY[cy] - 1);
    }

    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...