Submission #5393

#	Time	Username	Problem	Language	Result	Execution time	Memory
5393		baneling100	Star triangles (IZhO11_triangle)	C++98	18.18 / 100	188 ms	10460 KiB

triangle

#include <stdio.h>
#include <algorithm>
#define inf 0x7fffffff

using namespace std;

pair <int,int> p1[300002];
pair <int,int> p2[300002];
int n, xcnt[300001], ycnt[300001], px[300001], py[300001];
long long ans;

void input(void)
{
    int i, x, y;

    scanf("%d",&n);
    for(i=1 ; i<=n ; i++)
    {
        scanf("%d %d",&x,&y);
        p1[i]=make_pair(x,i);
        p2[i]=make_pair(y,i);
    }
    sort(p1+1,p1+n+1);
    sort(p2+1,p2+n+1);
}

void process(void)
{
    int i;

    p1[0].first=p2[0].first=inf;
    for(i=1 ; i<=n ; i++)
    {
        if(p1[i].first==p1[i-1].first)
            xcnt[i]=xcnt[i-1]+1;
        else
            xcnt[i]=1;
        if(p2[i].first==p2[i-1].first)
            ycnt[i]=ycnt[i-1]+1;
        else
            ycnt[i]=1;
    }
    for(i=n ; i>=1 ; i--)
    {
        if(xcnt[i]==xcnt[i+1]-1)
            xcnt[i]=xcnt[i+1];
        if(ycnt[i]==ycnt[i+1]-1)
            ycnt[i]=ycnt[i+1];
        px[p1[i].second]=xcnt[i];
        py[p2[i].second]=ycnt[i];
    }
    for(i=1 ; i<=n ; i++)
        ans+=((long long)px[i]-1)*(py[i]-1);
}

void output(void)
{
    printf("%lld",ans);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

• Subtask 1: 18.182 / 100