Submission #1090298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090298	2024-09-18T07:59:54 Z	maxFedorchuk	Star triangles (IZhO11_triangle)	C++17	100 / 100	454 ms	77204 KB

triangle

#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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	28508 KB	Output is correct
2	Correct	13 ms	28508 KB	Output is correct
3	Correct	13 ms	28460 KB	Output is correct
4	Correct	12 ms	28504 KB	Output is correct
5	Correct	11 ms	28476 KB	Output is correct
6	Correct	14 ms	28508 KB	Output is correct
7	Correct	13 ms	28436 KB	Output is correct
8	Correct	13 ms	28508 KB	Output is correct
9	Correct	12 ms	28508 KB	Output is correct
10	Correct	12 ms	28764 KB	Output is correct
11	Correct	12 ms	28764 KB	Output is correct
12	Correct	20 ms	30032 KB	Output is correct
13	Correct	20 ms	30040 KB	Output is correct
14	Correct	21 ms	30044 KB	Output is correct
15	Correct	133 ms	44808 KB	Output is correct
16	Correct	144 ms	46188 KB	Output is correct
17	Correct	139 ms	44880 KB	Output is correct
18	Correct	129 ms	44808 KB	Output is correct
19	Correct	416 ms	73648 KB	Output is correct
20	Correct	280 ms	61008 KB	Output is correct
21	Correct	443 ms	77140 KB	Output is correct
22	Correct	454 ms	77204 KB	Output is correct