39 - 餐廳評鑑

ForTest

題目：http://hoj.twbbs.org/judge/problem/view/39
AC Code：http://ideone.com/yhOc5k

今天我講的主題><
先照題目條件排序 接著做逆序數對
由於測資有點大 可是不想做離散化
所以code了Merge Sort做練習

Submission id:18647 Status:AC
http://hoj.twbbs.org/judge/judge/submission/18647

#include <iostream>

//#include <fstream>

#include <sstream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <algorithm>

//#include <map>

#include <stack>

#include <queue>

#include <vector>

//#include <deque>

#include <functional>

#include <ctime>

#include <cstdlib>

#include <iomanip>

using namespace std;

typedef long long LL;

#define F(a,b) for(int a=0;a<b;++a)

const int Max = 200001;

LL ans,k,m;;

pair<LL,LL> s[Max],tmp[Max];

void Count(int L,int M,int R){

    int i = L,j = M+1,pos = 0;

    while(i<=M && j<=R){

        if(s[i].first < s[j].first && s[i].second > s[j].second){

            tmp[pos++] = s[j++];

            ans += M - i + 1;

        }

        else tmp[pos++] = s[i++];

    }

    while(i <= M)tmp[pos++] = s[i++];

    while(j <= R)tmp[pos++] = s[j++];

    int now = 0;

    while(now < pos)s[L++] = tmp[now++];

}

void Divide(int L,int R){

    if(L == R)return;

    int M = (L+R)/2;

    Divide(L,M);

    Divide(M+1,R);

    Count(L,M,R);

}

int main(){

    while(~scanf("%lld%lld",&k,&m)){

        ans = 0;

        F(i,k)scanf("%lld",&s[i].first);

        F(i,k)scanf("%lld",&s[i].second);

        sort(s,s+k);

        Divide(0,(int)k-1);

        printf("%lld\n",ans);

    }

}