Submission #63601937

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define len(a) (int)((a).size())

#define int ll

int n;
vector<ll> a, b, c;

struct segtree {
    vector<ll> seg;
    int n;

    segtree(int n) : n(n) {
        seg.resize(n * 4);
    }

    void upd(int v, int l, int r, int pos, int val) {
        if (l == r - 1) {
            seg[v] += val;
        } else {
            int mid = (l + r) / 2;
            if (pos < mid) {
                upd(v * 2 + 1, l, mid, pos, val);
            } else {
                upd(v * 2 + 2, mid, r, pos, val);
            }
            seg[v] = seg[v * 2 + 1] + seg[v * 2 + 2];
        }
    }

    ll ask(int v, int l, int r, int askl, int askr) {
        if (l >= askr || askl >= r) return 0;
        if (askl <= l && r <= askr) return seg[v];
        int mid = (l + r) / 2;
        return ask(v * 2 + 1, l, mid, askl, askr) + ask(v * 2 + 2, mid, r, askl, askr);
    }
    void upd(int pos, int val) {
        upd(0, 0, n, pos, val);
    }
    ll ask(int askl, int askr) {
        return ask(0, 0, n, askl, askr);
    }
};

const ll SZ = 1'000'100;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    a.resize(n);
    b.resize(n);
    c.resize(n);
    for (auto &t : a) cin >> t;
    for (auto &t : b) cin >> t;
    for (auto &t : c) cin >> t;

    ll cur_cost = 0, ops = 0;
    segtree seg(SZ), segcnt(SZ), seg2(SZ), segcnt2(SZ);
    for (int i = 0; i < n; ++i) {
        if (a[i] == 1 && b[i] == 0) {
            cur_cost += seg.ask(0, c[i]);
            cur_cost += c[i] * (segcnt.ask(c[i], SZ));
            segcnt.upd(c[i], 1);
            seg.upd(c[i], c[i]);
            ++ops;
        } else if (a[i] == 0 && b[i] == 0) {
            continue;
        } else if (a[i] == 0 && b[i] == 1) {
            cur_cost += seg2.ask(0, c[i]);
            cur_cost += c[i] * (segcnt2.ask(c[i], SZ) + 1);
            segcnt2.upd(c[i], 1);
            seg2.upd(c[i], c[i]);
            ++ops;
        }
    }

    vector<pair<ll, ll>> vals;
    ll left_sum = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == 1 && b[i] == 1) {
            vals.push_back({c[i], i});
            left_sum += c[i];
        }
    }
    sort(rall(vals));
    ll ans = cur_cost + left_sum * ops;
    for (auto cc : vals) {
        int i = cc.second;
        cur_cost += seg.ask(0, c[i]);
        cur_cost += c[i] * (segcnt.ask(c[i], SZ));
        segcnt.upd(c[i], 1);
        seg.upd(c[i], c[i]);
        left_sum -= cc.first;
        cur_cost += seg2.ask(0, c[i]);
        cur_cost += c[i] * (segcnt2.ask(c[i], SZ) + 1);
        segcnt2.upd(c[i], 1);
        seg2.upd(c[i], c[i]);
        ops += 2;
        ans = min(ans, cur_cost + left_sum * ops);
    }

    cout << ans << "\n";

    return 0;
} 

Submission Info

Judge Result