记录编号	155420	评测结果	AAAAAAAAAA
题目名称	矩阵	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	2.520 s
提交时间	2015-03-28 21:18:09	内存使用	39.40 MiB

#include<cstdio>
char ci[15000000],co[14000000],*pi=ci,*po=co;
int tim,a[1001][1001],b[1000001],c[1000001];
inline short getint(short &x){
	short gg=0;
	while(*pi<'!'&&*pi>0) pi++;
	if(*pi<0) return 0;
	else if(*pi!=45) x=*pi-48;
	else gg=1,x=0;pi++;
	while(*pi>47) x=(x<<3)+(x<<1)+*pi++-48;
	if(gg) x=-x;
	return x;
}
inline int getint(int &x){
	short gg=0;
	while(*pi<'!'&&*pi>0) pi++;
	if(*pi<0) return 0;
	else if(*pi!=45) x=*pi-48;
	else gg=1,x=0;pi++;
	while(*pi>47) x=(x<<3)+(x<<1)+*pi++-48;
	if(gg) x=-x;
	return x;
}
inline void out(int x){
	static short f=0;
	static char p[10];
	while(x) p[++f]=x%10+'0',x/=10;
	while(f) *po++=p[f--];
}
inline int lowerbound(int x){
	int l=1,r=tim,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(b[mid]<x) l=mid+1;
		else r=mid-1;
	}
	return l;
}
inline void sort(int* a,const int &l,const int &r){
    if(l>=r) return;
    static int x,i,j;
    i=l,j=r,x=a[i];
    while(i<j){
        while(x<a[j]&&j>i) j--;
        if(i<j) a[i]=a[j],i++;
        while(x>a[i]&&j>i) i++;
        if(i<j) a[j]=a[i],j--;
    }
    a[i]=x,sort(a,l,i-1),sort(a,i+1,r);
}
int main(){
	freopen("matrixa.in","r",stdin);
	freopen("matrixa.out","w",stdout);
	int tmp=fread(pi,1,15000000,stdin),cnt;
	short n,m,d[1002];
	ci[tmp]=-1;
	while(getint(n)){
		getint(m),cnt=0,tim=1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				b[++cnt]=getint(a[i][j]),c[cnt]=1001;
		sort(b,1,cnt);
		for(int i=1;i<=m;i++) d[i]=0;
		for(int i=2;i<=cnt;i++) if(b[i]!=b[i-1]) b[++tim]=b[i];
		for(int i=1;i<=n;i++){
			cnt=0;
			for(int j=1;j<=m;j++){
				a[i][j]=lowerbound(a[i][j]);
				if(c[a[i][j]]<=j) out(cnt+=d[j]),*po++=' ';
				else d[c[a[i][j]]]--,c[a[i][j]]=j,out(cnt+=++d[j]),*po++=' ';
			}
			*po++='\n';
		}
	}
	fwrite(co,1,po-co,stdout);
}