Submission #1624942

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>

using namespace std;
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

int bsr(uint x) { return 31 - __builtin_clz(x); }

template<class T>
struct Fenwick {
    int N, lg;
    V<T> seg;
    Fenwick() {}
    Fenwick(int N) : N(N) {
        seg = V<T>(N+1);
        lg = bsr(uint(N));
        fill(begin(seg), end(seg), T(0));
    }
    void add(int i, T x) {
        i++;
        while (i <= N) {
            seg[i] += x;
            i += i & -i;
        }
    }

    T sum(int i) {
        T s{0};
        while (i > 0) {
            s += seg[i];
            i -= i & -i;
        }
        return s;
    }

    T sum(int a, int b) {
        return sum(b) - sum(a);
    }
};

const int MN = 100100;
struct D {
    ll b, w;
};

ll C;
D d[MN];
D e[MN];

ll calc(int l, int r) {
    if (l+1 == r) return 0;
    int md = (l+r)/2;
    int sl = l, tl = md;
    int sr = md, tr = r;
    ll sm = calc(sl, tl) + calc(sr, tr);
    V<ll> v;
    for (int i = sr; i < tr; i++) {
        v.push_back(d[i].w);
    }
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
    int U = int(v.size());
    auto getI = [&](ll x) {
        return lower_bound(begin(v), end(v), x) - begin(v);
    };
    Fenwick<ll> fw1(U), fww(U);

    int cnt = l;
    V<D> back;
    while (true) {
        bool f1 = (sl == tl);
        bool f2 = (sr == tr);
        bool f3 = !f1 & !f2;
        if (f1 & f2) break;
        if (f2 || (f3 && d[sl].b < d[sr].b)) {
            D x = d[sl];
/*            ll sm1 = 0;
            for (D y: back) {
                sm1 += max(x.w, y.w);
                sm1 += min(x.w, y.w) * C;
            }
            sm += sm1;*/
            int p = getI(x.w);
            ll sm2 = 0;
            //x<=y, min
            sm2 += fw1.sum(p, U) * x.w * C;
            //x<=y, max
            sm2 += fww.sum(p, U);
            //y<=x, min
            sm2 += fww.sum(0, p) * C;
            //y<=x, max
            sm2 += fw1.sum(0, p) * x.w;
//            cout << sm1 << ", " << sm2 << endl;

            sm += sm2;

            e[cnt++] = d[sl++];
        } else if (f1 || (f3 && d[sl].b > d[sr].b)) {
            back.push_back(d[sr]);
            fw1.add(getI(d[sr].w), 1);
            fww.add(getI(d[sr].w), d[sr].w);
            e[cnt++] = d[sr++];
        } else {
            assert(false);
        }
    }
    assert(cnt == r);
    copy_n(e+l, r-l, d+l);
    return sm;
}

int main() {
    int n;
    cin >> n >> C;
    for (int i = 0; i < n; i++) {
        ll b, w;
        cin >> b >> w;
        d[i] = D{b, w};
    }
    cout << calc(0, n) << endl;
/*
    for (int i = 0; i < n; i++) {
        cout << d[i].b << ", " << d[i].w << endl;
    }*/
    return 0;
}

Submission Info

Judge Result