Cod sursa(job #264713)

Utilizator BaduBadu Badu Badu Data 22 februarie 2009 17:07:31
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
#define btgr 60
#define N 4096

long long n,m;
long long BIT[4096][64],triplete;

long long bit_count(long long a,long long b){
	long long i,nr,cat=0;
	long long gr = n/btgr + 1;

	for(i=1;i<=gr;i++){
		nr = BIT[a][i] & BIT[b][i];

		for(;nr;nr>>=1,cat+=nr&1?1:0);
	}
	return cat;
}
long longmain(){

	freopen("triplete.in","rt",stdin);
	freopen("triplete.out","wt",stdout);
	long long x,y,i,k,j,gr,how,ordine;
	scanf("%d%d",&n,&m);
	for(;m--;){
		scanf("%d%d",&x,&y);
		BIT[x][0]++;
		gr = y/btgr + 1;
		ordine =y%btgr;
		how = 1<<(btgr - ordine);
		BIT[x][gr] ^= how;
	}
	gr = n/btgr + 1;
	for(i=1;i<=n;i++){
	if(BIT[i][0]){
		for(j=1;j<=gr;j++){
			for(k=btgr-1;k>=1;k--){
				if(BIT[i][j] & 1<<k){
					if(j==1) how = btgr - k;
					else how = (j-1)*btgr + btgr - k;
					triplete+=bit_count(i,how);
				}
			}if(j>1) if(BIT[i][j] & 1<<btgr) triplete+=bit_count(i,(j-1)*btgr);
		}
	}

	}


	
	printf("%lld",triplete);			
	return 0;
}