제출 #1289647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289647		MinhKien	별들과 삼각형 (IZhO11_triangle)	C++20	100 / 100	147 ms	5756 KiB

triangle

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 3e5 + 10;

int n, x[N], y[N];
vector <int> X, Y;

void compress(vector <int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

int id(vector <int> &v, int val) {
    return lower_bound(v.begin(), v.end(), val) - v.begin();
}

int cntX[N], cntY[N];

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        X.push_back(x[i]);
        Y.push_back(y[i]);
    }

    compress(X);
    compress(Y);

    for (int i = 1; i <= n; ++i) {
        x[i] = id(X, x[i]);
        y[i] = id(Y, y[i]);
        ++cntX[x[i]];
        ++cntY[y[i]];
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += 1ll * (cntX[x[i]] - 1) * (cntY[y[i]] - 1);
    }

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 100 / 100