Submission #1169475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169475		AlgorithmWarrior	Star triangles (IZhO11_triangle)	C++20	100 / 100	251 ms	7460 KiB

triangle

#include <bits/stdc++.h>

using namespace std;

int const MAX=3e5+5;
int n;
struct point{
    int x,y,sus,jos,st,dr;
}pct[MAX];

bool cmp1(point a,point b){
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}

bool cmp2(point a,point b){
    if(a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}

void read(){
    cin>>n;
    int i;
    pct[0].x=-2e9;
    pct[0].y=-2e9;
    pct[n+1].x=2e9;
    pct[n+1].y=2e9;
    for(i=1;i<=n;++i)
        cin>>pct[i].x>>pct[i].y;
}

void precalc(){
    int i;
    sort(pct+1,pct+n+1,cmp1);
    for(i=1;i<=n;++i)
        if(pct[i].x==pct[i-1].x)
            pct[i].jos=pct[i-1].jos+1;
    for(i=n;i;--i)
        if(pct[i].x==pct[i+1].x)
            pct[i].sus=pct[i+1].sus+1;
    sort(pct+1,pct+n+1,cmp2);
    for(i=1;i<=n;++i)
        if(pct[i].y==pct[i-1].y)
            pct[i].st=pct[i-1].st+1;
    for(i=n;i;--i)
        if(pct[i].y==pct[i+1].y)
            pct[i].dr=pct[i+1].dr+1;
}

long long solve(){
    int i;
    long long rez=0;
    for(i=1;i<=n;++i){
        rez+=1LL*pct[i].st*pct[i].sus;
        rez+=1LL*pct[i].sus*pct[i].dr;
        rez+=1LL*pct[i].dr*pct[i].jos;
        rez+=1LL*pct[i].jos*pct[i].st;
    }
    return rez;
}

int main()
{
    read();
    precalc();
    cout<<solve();
    return 0;
}

• Subtask 1: 100 / 100