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