oj.uz

Submission #5393

# Submission time Handle Problem Language Result Execution time Memory
5393 2014-04-26T19:05:26 Z baneling100 Star triangles (IZhO11_triangle) C++
18.18 / 100
 188 ms 10460 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10460 KB Output is correct
2 Correct 0 ms 10460 KB Output is correct
3 Correct 0 ms 10460 KB Output is correct
4 Incorrect 0 ms 10460 KB Output isn't correct
5 Correct 0 ms 10460 KB Output is correct
6 Incorrect 0 ms 10460 KB Output isn't correct
7 Incorrect 0 ms 10460 KB Output isn't correct
8 Incorrect 0 ms 10460 KB Output isn't correct
9 Incorrect 0 ms 10460 KB Output isn't correct
10 Incorrect 0 ms 10460 KB Output isn't correct
11 Incorrect 0 ms 10460 KB Output isn't correct
12 Incorrect 8 ms 10460 KB Output isn't correct
13 Incorrect 8 ms 10460 KB Output isn't correct
14 Incorrect 0 ms 10460 KB Output isn't correct
15 Incorrect 60 ms 10460 KB Output isn't correct
16 Incorrect 60 ms 10460 KB Output isn't correct
17 Incorrect 48 ms 10460 KB Output isn't correct
18 Incorrect 52 ms 10460 KB Output isn't correct
19 Incorrect 144 ms 10460 KB Output isn't correct
20 Incorrect 116 ms 10460 KB Output isn't correct
21 Incorrect 188 ms 10460 KB Output isn't correct
22 Incorrect 176 ms 10460 KB Output isn't correct