제출 #1324448

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

triangle

#include <iostream>
#include <vector>
#include <map>

using namespace std;

/**
 * Masala: To'g'ri burchakli uchburchaklar
 * Vaqt murakkabligi: O(N log N)
 */

int main() {
    // Kiritish va chiqarishni tezlashtirish
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int, int>> stars(n);
    map<int, int> countX, countY;

    // Har bir koordinata bo'yicha yulduzlar sonini hisoblash
    for (int i = 0; i < n; i++) {
        cin >> stars[i].first >> stars[i].second;
        countX[stars[i].first]++;
        countY[stars[i].second]++;
    }

    long long total_triangles = 0;

    // Har bir yulduzni to'g'ri burchak cho'qqisi sifatida tekshirish
    for (int i = 0; i < n; i++) {
        long long currentX = countX[stars[i].first];
        long long currentY = countY[stars[i].second];
        
        // (nx - 1) * (ny - 1) formula orqali uchburchaklar sonini qo'shish
        total_triangles += (currentX - 1) * (currentY - 1);
    }

    cout << total_triangles << endl;

    return 0;
}

• Subtask 1: 100 / 100