Poj Solution 1990

http://poj.org/problem?id=1990

//* @author: 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
/*
 *�ο���ţ�ij���,��һ��д��״����...
 *�Ƚ�cows��volumeΪ�ؼ�������..
 *}����״����,һ��ά�������,һ��ά��ǰ����С�ڵ�ǰ������֮��
 */
class cin
{
 static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
 static StringTokenizer st;
 static int leave=0;
 static int nextInt() throws IOException
 {
  while(leave==0)
  {
   st=new StringTokenizer(in.readLine());
   leave=st.countTokens();
  }
  leave--;
  return Integer.parseInt(st.nextToken());
 }
 static boolean hasNext() throws IOException
 {
  while(leave==0)
  {
   String temp=in.readLine();
   if(temp==null)return false;
   st=new StringTokenizer(temp);
   leave=st.countTokens();
  }
  return true;
 }
}

class TreeArray 
{
    int value[],n;
    TreeArray(int num)
    {
     n=num;
     value=new int[n+1];
     Arrays.fill(value,0);
    }
    
    int lowBit(int t)
    {
     return t&(t^(t-1));
    }
    
    void plus(int a,int i)
    {
     while(i<=n)
     {
      value[i]+=a;
         i+=lowBit(i);
     }
    }
    
    int getSum(int i)
    {
     int sum=0;
     while(i>0)
     {
      sum+=value[i];
      i=i-lowBit(i);
     }
     return sum;
    }   
}

class Moo
{
 int x,v;
 Moo(int a,int b)
 {
  v=a;x=b;
 }
}

class Cmp implements Comparator< Object>
{
 public int compare(Object a,Object b)
 {
  if(((Moo)a).v>((Moo)b).v)return 1;
  return -1;
 }
}

class MooFest
{
 TreeArray count,total;
 long sum=0,now=0;
 int n,i;
 Moo cow[];
 MooFest() throws IOException
 {
  n=cin.nextInt();
  cow=new Moo[n+1];
  count=new TreeArray(20000);
  total=new TreeArray(20000);
  for(i=1;i<=n;i++)
  {
   cow[i]=new Moo(cin.nextInt(),cin.nextInt());
  }
  Arrays.sort(cow,1,n+1,new Cmp());
 }
 
 long totalV()
 {
  int c,t;
  for(i=1;i<=n;i++)
  {
   now+=cow[i].x;
   count.plus(1,cow[i].x);
   total.plus(cow[i].x,cow[i].x);
   c=count.getSum(cow[i].x);
   t=total.getSum(cow[i].x);
   sum+=(long)(2*c*cow[i].x-2*t+now-i*cow[i].x)*cow[i].v;
  }
  return sum;
 }
}
public class Main {
     public static void main(String args[]) throws IOException
     {
      MooFest data=new MooFest();
      System.out.println(data.totalV());
     }
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *