京都大学プログラミングコンテスト2015 G - ケンドー

問題

kupc2015.contest.atcoder.jp

解法

配列 B の後ろから順に対応する A の数字を決めていきます。今, B[i] に対応する A[j] を決定したいとすると, j は, まだ配列 B の要素とまだ対応していない j の中で, 一番右側にあるものを選べば良いです。

これを高速に実行するために, Binary Indexed Tree および priority_queue を使います。B[i] を見ている時点で A[j] >= B[i] を満たしている, まだ対戦相手の決まっていない j を priority_queue に突っ込んでおき, 一番右側にあるものを選びます。で, よくある BIT の使い方をすれば良いです。

BIT 使うんだろうなとは思ったんですが priority_queue を使う発想がなくて解けませんでした…

// 0-based Binary Indexed Tree
// 数え上げ用
constexpr int mod = 1e9+7;
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s += bit[i]) %= mod;
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] += x) %= mod;
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)-sum(a);
    }
    // sum(0, i) >= wとなる最小のiを求める 存在しなければmaxを返す
    int lb(T w) {
        if (w <= 0) return 0;
        int k = 1;
        while (k <= max) k <<= 1;
        int i = 0;
        for (; k > 0; k >>= 1) if (i+k <= max && bit[i+k] < w) {
            w -= bit[i+k];
            i += k;
        }
        return i+1;
    }
};

const int MAXN = 100010;
int A[MAXN], B[MAXN];
pii P[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    for (int i = 0; i < N; i++) {
        P[i] = pii(A[i], i);
    }
    sort(P, P+N);
    BIT<ll> bit(N);
    for (int i = 0; i < N; i++) bit.add(i, 1);
    priority_queue<int> que;
    int cur = N-1;
    ll ans = 0;
    for (int i = N-1; i >= 0; i--) {
        while (cur >= 0 && P[cur].first >= B[i]) {
            que.push(P[cur--].second);
        }
        if (que.empty()) {
            cout << -1 << endl;
            return 0;
        }
        int tmp = que.top(); que.pop();
        ans += bit.sum(N) - bit.sum(tmp) - 1;
        bit.add(tmp, -1);
    }
    cout << ans << endl;
    return 0;
}