Poj Solution 2380

http://poj.org/problem?id=2380

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


#define INF 30000
#define NMAX 500003
typedef struct
{
    long q,s,v;
}data;
data a[NMAX];
data b[NMAX];
long y[NMAX];
long x[NMAX];
long N;
int cmp(const void *a,const void *b)
{
    if(((data*)a)->s==((data*)b)->s)
        return ((data*)a)->q-((data*)b)->q;
    else
        return ((data*)a)->s-((data*)b)->s;
}
int cmp2(const void *a,const void *b)
{
    if(((data*)a)->q==((data*)b)->q)
        return ((data*)a)->s-((data*)b)->s;
    else
        return ((data*)a)->q-((data*)b)->q;
}
void solve()
{
    int i,j,k,nmax,ymax,xmax;
    qsort(a,N,sizeof(data),cmp);
    y[0]=a[0].s;
    
    j=0;
    b[0].s=a[0].s;
    b[0].q=a[0].q;
    b[0].v+=a[0].v;
    k=0;
    for(i=1;i<N;i++)
    {
        if(a[i].s==a[i-1].s&&a[i].q==a[i-1].q)
        {
            b[j].s=a[i].s;
            b[j].q=a[i].q;
            b[j].v+=a[i].v;
        }
        else
        {
            j++;
            b[j].s=a[i].s;
            b[j].q=a[i].q;
            b[j].v+=a[i].v;
        }
        if(a[i].s>y[k])
        {
            y[++k]=a[i].s;
        }
    }
    ymax=k+1;
    nmax=j+1;
    qsort(b,nmax,sizeof(data),cmp2);
    x[0]=b[0].q;
    k=0;
    for(i=1;i<nmax;i++)
    {
        if(b[i].q>x[k])
            x[++k]=b[i].q;
    }
    xmax=k+1;
    qsort(b,nmax,sizeof(data),cmp);

    
    printf("-1 ");
    for(i=0;i<xmax;i++)
    {
        printf("%d",x[i]);
        if(i<xmax-1)
            printf(" ");
        else
            printf("n");
    }
    k=0;
    for(i=0;i<ymax;i++)
    {
        printf("%d ",y[i]);
        for(j=0;j<xmax;j++)
        {
            if(b[k].q==x[j]&&b[k].s==y[i])
                printf("%d",b[k++].v);
            else
                printf("0");
            if(j<xmax-1)
                printf(" ");
            else
                printf("n");
        }
    }


}

int main()
{
    
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    scanf("%d",&N);
    long i;
    for(i=0;i<N;i++)
    {
        scanf("%d%d%d",&a[i].q,&a[i].s,&a[i].v);
    }
    
    solve();

#if debug
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *