Submission #1090298

#TimeUsernameProblemLanguageResultExecution timeMemory
1090298maxFedorchukStar triangles (IZhO11_triangle)C++17
100 / 100
454 ms77204 KiB
#include <bits/stdc++.h>
using namespace std;

const long long MX=3e5+10;
long long x[MX],y[MX];
long long n;

void compr(long long *o)
{
    map < long long , long long > mp;
    for(long long i=1;i<=n;i++)
    {
        mp[o[i]]=1;
    }

    long long uk=0;
    for(auto & u:mp)
    {
        uk++;
        u.second=uk;
    }

    for(long long i=1;i<=n;i++)
    {
        o[i]=mp[o[i]];
    }
}

set < pair < long long , long long > > corgor[MX];
set < pair < long long , long long > > corver[MX];

long long chk(long long corx,long long cory)
{
    return (corgor[corx].size()-1)*(corver[cory].size()-1);
}

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

    cin>>n;

    for(long long i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }

    compr(x);
    compr(y);
/*
    for(long long i=1;i<=n;i++)
    {
        cout<<x[i]<<" "<<y[i]<<"\n";
    }
    cout<<"\n";
*/
    for(int i=1;i<=n;i++)
    {
        corgor[x[i]].insert({y[i],0});
        corver[y[i]].insert({x[i],0});
    }
/*
    for(int i=1;i<=n;i++)
    {
        set < pair < int , int > > rrrr;
        int uk;

        uk=0;
        for(auto & u:corgor[i])
        {
            uk++;

            auto zn=u;
            zn.second=uk;

            rrrr.insert(zn);
        }
        corgor[i].clear();
        corgor[i]=rrrr;
        rrrr.clear();


        uk=0;
        for(auto & u:corver[i])
        {
            uk++;

            auto zn=u;
            zn.second=uk;

            rrrr.insert(zn);
        }
        corver[i].clear();
        corver[i]=rrrr;
        rrrr.clear();
    }
*/
    long long ans=0;
    for(long long i=1;i<=n;i++)
    {
        ans+=chk(x[i],y[i]);
    }

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