# Poj Solution 3067

```http://poj.org/problem?id=3067

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
static long ans=0;
public static void main(String[] args) throws IOException
{
int cnt=0;
while((a--)!=0)
{
ans=0;
cnt++;
int n=Integer.parseInt(ss[2]);
my[] p=new my[n];
for(int i=0;i< n;i++)
{
int x1=Integer.parseInt(ss[0]);
int y1=Integer.parseInt(ss[1]);
p[i]=new my(x1,y1);
}
Arrays.sort(p);
mergesort(p,0,n);
System.out.println("Test case "+cnt+": "+ans);
}
}

static void mergesort(my[] arr,int f,int n)
{
int n1,n2;
if(n>1)
{
n1=n/2;
n2=n-n1;
mergesort(arr,f,n1);
mergesort(arr,f+n1,n2);
merge(arr,f,n1,n2);
}
}

static void merge(my[] arr,int f,int n1,int n2)
{
int[] temp=new int[n1+n2];
int cp=0,cp1=0,cp2=0,i=0;
while((cp1< n1)&&(cp2< n2))
{
if(arr[f+cp1].y< arr[f+n1+cp2].y)
temp[cp++]=arr[f+(cp1++)].y;
else if (arr[f+cp1].y==arr[f+n1+cp2].y)
{
temp[cp++]=arr[f+(cp1++)].y;
}
else {
temp[cp++]=arr[f+n1+(cp2++)].y;
ans+=n1-cp1;
}
}
while(cp1< n1)
temp[cp++]=arr[f+(cp1++)].y;
while(cp2< n2)
temp[cp++]=arr[f+n1+(cp2++)].y;
for(i=0;i< cp;i++)
arr[f+i].y=temp[i];
}
}

class my implements Comparable< my>
{
int x,y;
public my(int a,int b)
{
x=a;
y=b;
}
public int compareTo(my arg0) {
if(x==arg0.x)
return y-arg0.y;
return x-arg0.x;
}
}
```
This entry was posted in poj. Bookmark the permalink.