【題解】ZeroJudge a457: TOI2010 第五題:餐廳評鑑

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a457

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 100005;
int k, m, bit[maxn], a[maxn], b[maxn], x[maxn];
long long ans;
vector <int> v;

bool cmp(int i, int j){
    if (a[i] != a[j]) return a[i] > a[j];
    return b[i] >= b[j];
}
void update(int x){
    while (x <= (int)v.size()){
        bit[x]++;
        x += x & (-x);
    }
}
int query(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}

int main() {
    cin >> k >> m;
    for (int i = 1; i <= k; i++){
        cin >> a[i];
        x[i] = i;
    }
    for (int i = 1; i <= k; i++){
        cin >> b[i];
        v.push_back(b[i]);
    }
    sort(x+1, x+k+1, cmp);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= k; i++){
        int tmp = lower_bound(v.begin(), v.end(), b[x[i]])-v.begin()+1;
        ans += query(tmp-1);
        update(tmp);
    }
    cout << ans << "\n";
}
分享本文 Share with friends