Submission #534903

---

Source Code Expand

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>

using namespace std;
typedef long long li;
typedef long double real;

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

const li bit_max = 1e5 + 10;
li bit[bit_max + 1];
li sum(int i) {
    li s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, li x) {
    while (i <= bit_max) {
        bit[i] += x;
        i += i & -i;
    }
}

int main() {
    li n;
    cin >> n;
    vector<li> a(n), b(n);
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n) {
        cin >> b[i];
    }
    priority_queue<pair<li, li>> q;
    rep(i, n) {
        q.emplace(a[i], i);
    }

    li ans = 0;
    priority_queue<int> cands;
    for (li i = n-1; i >= 0; --i) {
        while (not q.empty() && q.top().first >= b[i]) {
            cands.emplace(q.top().second);
            //cerr << "ins " << q.top().second << endl;
            q.pop();
        }
        if (cands.empty()) {
            cout << -1 << endl;
            return 0;
        }
        ans += i - cands.top() + sum(cands.top() + 1);
        add(cands.top() + 1, 1);
        //cerr << "out " << cands.top() << ", ans = " << ans << endl;
        cands.pop();
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result