Cod sursa(job #75581)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 3 august 2007 16:38:58
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
# include <stdio.h>
# include <stdlib.h>

const long int MAXM=80000;
typedef struct NOD {long int inf; NOD *drta,*stga;};
NOD *rad;
long int n,bat[10001];

long int max(long int a, long int b) {if (a>b) return a; return b;}

void aloca_arb_dint(long int li, long int lf, NOD *p)
{
(*p).inf=0;
if (li!=lf)
	{
	NOD *q;
	long int m=(li+lf)/2;
	q=(NOD*) malloc (sizeof(NOD));
	(*q).drta=NULL;
	(*q).stga=NULL;
	(*q).inf=0;
	(*p).stga=q;
	aloca_arb_dint(li,m,(*p).stga);
	q=(NOD*) malloc (sizeof(NOD));
	(*q).drta=NULL;
	(*q).stga=NULL;
	(*q).inf=0;
	(*p).drta=q;
	aloca_arb_dint(m+1,lf,(*p).drta);
	}
}

void update_arb_dint(long int li, long int lf, NOD *p, long int a)
{
(*p).inf++;
if (li!=lf)
	{
	long int m=(li+lf)/2;
	if (a<=m) update_arb_dint(li,m,(*p).stga,a);
	else update_arb_dint(m+1,lf,(*p).drta,a);
	}
}


void citire()
{
FILE *f=fopen("nrtri.in","r");
fscanf(f,"%ld",&n);
long int i;
for (i=1;i<=n;i++)
	{
	fscanf(f,"%ld",&bat[i]);
	update_arb_dint(1,MAXM,rad,bat[i]);
	}
fclose(f);
}

void scrie(long int sol)
{
FILE *g=fopen("nrtri.out","w");
fprintf(g,"%ld\n",sol);
fcloseall();
}

long int querry(long int li, long int lf, NOD *p, long int a, long int b)
{
long int m=(li+lf)/2;
if (li==a&&lf==b) return (*p).inf;
else
	{
	if (b<=m) return querry(li,m,(*p).stga,a,b);
	else if (a>=m+1) return querry(m+1,lf,(*p).drta,a,b);
	else return querry(li,m,(*p).stga,a,m)+querry(m+1,lf,(*p).drta,m+1,b);
	}
}

int main()
{
rad=(NOD*) malloc (sizeof(NOD));
(*rad).inf=0;(*rad).stga=NULL;(*rad).drta=NULL;
aloca_arb_dint(1,MAXM,rad);
citire();
long int sol=0,corectie,i,j,minim,maxim;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
if (i!=j)
	{
	minim=max(bat[i]-bat[j],bat[j]-bat[i]);
	maxim=bat[i]+bat[j];
	corectie=0;
	if (minim<=bat[i]&&maxim>=bat[i]) corectie++;
	if (minim<=bat[j]&&maxim>=bat[j]) corectie++;
	sol+=querry(1,MAXM,rad,max(minim,1),maxim)-corectie;
	}
scrie(sol/3);
return 0;
}