2013年7月2日 星期二

TOI2010 第五題:餐廳評鑑 (ZJ a457)

/*
    題目連結
*/
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct s
{
    long long int x, y;
}B[100000], C[100000];
long long int merge(int a, int b, int lth)
{
    if( lth == 1 ){ return 0; }
    int v = (a+b)/2; int vth = (a+b)/2-a;
    int uth = lth - vth;
    long long int re = merge(a, v, vth);
    re += merge(v, b, uth);
    int left = vth;
    int ai = a; int vi = v;
    for(int i = a; i < b; i++)
    {
        if( ai == v ){ C[i] = B[vi++]; }
        else if( vi == b ){ C[i] = B[ai++]; left--;}
        else
        {
            if( B[vi].y > B[ai].y ){ C[i] = B[vi++]; re += left; }
            else{ C[i] = B[ai++]; left--;}
        }
    }
    for(int i = a; i < b; i++){ B[i] = C[i]; }
    return re;
}
bool cmp(s a,s b)
{
    if( a.x > b.x ){ return 1; } if( a.x < b.x ){ return 0; }
    if( a.y > b.y ){ return 1; } return 0;  
}
int main()
{
    int k; long long int m; scanf("%d %lld", &k, &m);
    for(int i = 0; i < k; i++) scanf("%lld", &B[i].x);
    for(int i = 0; i < k; i++) scanf("%lld", &B[i].y);
    sort(B,B+k,cmp);
    printf("%lld\n", merge(0,k,k)); //system("pause");
}

沒有留言:

張貼留言