Submission #1115540

#TimeUsernameProblemLanguageResultExecution timeMemory
1115540LeonidCukStar triangles (IZhO11_triangle)C++17
100 / 100
209 ms13492 KiB
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int>&a,pair<int,int>&b)
{
    if(a.first==b.first)return a.second<b.second;
    return a.first<b.first;
}
int main()
{
    int n,a,b;
    cin>>n;
    vector<pair<int,int>>v;
    unordered_map<int,int>m,m1;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end(),cmp);
    int i=0;
    long long int sum=0;
    while(i<n)
    {
        pair<int,int>p=v[i];
        int j=i+1;
        int cnt=1;
        while(j<n&&v[j].first==p.first)
        {
            cnt++;
            j++;
        }
        while(i<j)
        {
            sum+=m[v[i].second];
            sum+=m1[v[i].second]*(cnt-1);
            m1[v[i].second]++;
            m[v[i].second]+=(cnt-1);
            i++;
        }
    }
    cout<<sum;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...