记录编号	155409	评测结果	AAAAAAAAAA
题目名称	矩阵	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.740 s
提交时间	2015-03-28 20:36:16	内存使用	59.42 MiB

#include<cstdio>
char co[50000000],*po=co;
int tim,a[1001][1001],b[1000001],c[1000001];
inline short getint(short &x){
	short ch,gg=0;
	while(ch=getchar(),ch<40&&ch!=EOF);
	if(ch==EOF) return 0;
	else if(ch!=45) x=ch-48;
	else gg=1,x=0;
	while((ch=getchar())>47) x=(x<<1)+(x<<3)+ch-48;
	if(gg) x=-x;
	return x;
}
inline int getint(int &x){
	short ch,gg=0;
	while(ch=getchar(),ch<40&&ch!=EOF);
	if(ch==EOF) return 0;
	else if(ch!=45) x=ch-48;
	else gg=1,x=0;
	while((ch=getchar())>47) x=(x<<1)+(x<<3)+ch-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(const 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);
	short n,m;
	int d[1002],cnt;
	while(getint(n)){
		getint(m),cnt=0,tim=1;
		short j;
		for(short i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				b[++cnt]=getint(a[i][j]),c[cnt]=1001;
		sort(b,1,cnt);
		for(short 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];
		short i;
		for(i=1;i<=n;i++){
			cnt=0;
			for(j=1;j<=m;j++){
				a[i][j]=lowerbound(a[i][j]);
				if(c[a[i][j]]<=j) out(cnt+=d[j]);
				else d[c[a[i][j]]]--,c[a[i][j]]=j,out(cnt+=++d[j]);
				*po++=' ';
			}
			*po++='\n';
		}
	}
	fwrite(co,1,po-co,stdout);
}