Submission #1324448

#TimeUsernameProblemLanguageResultExecution timeMemory
1324448sh_qaxxorov_571Star triangles (IZhO11_triangle)C++20
100 / 100
333 ms5848 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...