[HOJ] 39 - 餐廳評鑑

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
#define low(x) (x&-x)
#define N 100005
struct P{
    int x,y;
}s[N];
int cmp1(P a,P b){
    return a.y<b.y;
}
int cmp(P a,P b){
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
map<int,int> ma;
int c[N]={0},n;
void add(int k){
    for(int i=k;i<=n;i+=low(i))
        c[i]++;
}
int cnt(int k){
    int ans=0;
    for(int i=k;i>0;i-=low(i))
        ans+=c[i];
    return ans;
}
int main(){
    int k,i,p;
    long long int ans=0;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++)
        scanf("%d",&s[i].x);
    for(i=0;i<n;i++)
        scanf("%d",&s[i].y);
    sort(s,s+n,cmp1);
    for(i=0;i<n;i++){
        if(ma.find(s[i].y)==ma.end())
            ma[s[i].y]=i+1;
        s[i].y=ma[s[i].y];
    }

    sort(s,s+n,cmp);
    for(i=0;i<n;i++){
        add(s[i].y);
        p=cnt(s[i].y);
        ans+=i-p+1;
    }
    printf("%lld\n",ans);
}