[POJ] 3067 Japan 2.cpp

#include<cstdio>
#include<algorithm>
using namespace std;

struct city{
    int e;
    int w;
};

bool cmp(city a,city b);
void mergesort(int l,int h,city a[]);
void combine(int l,int mid,int h,city a[]);

long long int cross=0;
int buffer[500001];


int main()
{
    int T,t,N,M,K,k,i;
    scanf("%d",&T);
    for(t=1;t<=T;t++)
    {
        city a[100000]; cross=0;

        scanf("%d %d %d",&N,&M,&K);
        for(k=0;k<K;k++)
            scanf("%d %d",&a[k].e,&a[k].w);

        sort(a,a+K,cmp);
        mergesort(0,k-1,a);

        printf("Test case %d: %lld\n",t,cross);
    }
    return 0;
}
bool cmp(city a,city b)
{
    if (a.e==b.e) return a.w<b.w;
    return a.e<b.e;
}
void mergesort(int l,int h,city a[])
{
    if(l==h) return;
    int mid=(l+h)/2;
    mergesort(l,mid,a);
    mergesort(mid+1,h,a);
    combine(l,mid,h,a);
}
void combine(int l,int mid,int h,city a[])
{
    int lcnt=l,hcnt=mid+1,bufcnt=0;
    while(lcnt<=mid && hcnt<=h){
        if(a[hcnt].w<a[lcnt].w){
            buffer[bufcnt++]=a[hcnt++].w;
            cross+=(mid-lcnt+1);
        }
        else buffer[bufcnt++]=a[lcnt++].w;
    }
    while(lcnt<=mid) buffer[bufcnt++]=a[lcnt++].w;
    while(hcnt<=h) buffer[bufcnt++]=a[hcnt++].w;
    for(bufcnt=0;l<=h;l++)
        a[l].w=buffer[bufcnt++];
}