1990.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 #include"iostream.h"
 #include"stdio.h"
 #include"math.h"
 #include<vector>
 #include<algorithm>
 using namespace std;



 const long size=20000;
	 //20000;

 long p_sum[size+10];
 long person[size+10];

 long sum,cows;

 void insert(long a,long b,long v)
 {
	 if(a>b)return;
	 long c=(a+b)/2;
	 
	 if(c==v)
	 {
		 if(a<c)
		 {sum+=p_sum[(a+c-1)/2];cows+=person[(a+c-1)/2];}
	 }
	 else if(v<c)insert(a,c-1,v);
	 else 
	 {
		 sum+=p_sum[c];cows+=person[c];
		 //if(v<b)
		 {
			 sum-=p_sum[(b+c+1)/2];
			 cows-=person[(b+c+1)/2];
		 }
		
		insert(c+1,b,v);
	 }
	
	 p_sum[c]+=v; 
	 person[c]++;
	 return;
 }
 struct cowtype
 {
	 long value,position;
 }cow[20010];

 int cmp(cowtype a,cowtype b)
 {
	 return a.value<b.value;
 }

 long n;
 int main()
 {
	 long i;
	 __int64 answer;
	 scanf("%ld",&n);
	 
	 for(i=0;i<n;i++)
		 scanf("%ld %ld",&cow[i].value,&cow[i].position);

	 sort(&cow[0],&cow[n],cmp);

	for(i=0;i<size+10;i++)p_sum[i]=0;

	 for(answer=0,i=0;i<n;i++)
	 {
		 sum=0;cows=0;
		 insert(1,size,cow[i].position);
		 answer+=(__int64)(cow[i].position*cows-sum+p_sum[(size+1)/2]-cow[i].position-sum-cow[i].position*(i-cows))*(__int64)cow[i].value;
	 }

	 printf("%I64d\n",answer);
	 return 0;
 }