Solution for https://codeforces.com/contest/1334/problem/F

sol.cc

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define FOR(i, j, k, in) for (int i = j; i < k; i += in)
#define RFOR(i, j, k, in) for (int i = j; i >= k; i -= in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)

struct segment_tree {
    /*  What can you do with this:
        - update a range by adding a value to each element in the range.
        - set a single element's value
        - query a single element's value
    */
    ll n;
    vector<ll> vec;

    segment_tree(ll _n) : n{_n} {
        vec.assign(4 * n, 0ll);
    }

    void update(ll pos, ll tl, ll tr, ll l, ll r, ll v) {
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r)
            vec[pos] += v;
        else {
            ll tm = (tl + tr) / 2ll;
            if (l <= tm) update(2ll * pos, tl, tm, l, r, v);
            if (tm + 1 <= r) update(2ll * pos + 1ll, tm + 1ll, tr, l, r, v);
        }
    }

    void add(ll l, ll r, ll value) {
        update(1, 0, n, l, r, value);
    }

    void set_single(ll pos, ll tl, ll tr, ll x, ll v) {
        if (tl == tr) {
            vec[pos] = v;
            return;
        }
        ll tm = (tl + tr) / 2ll;
        v -= vec[pos];
        if (x <= tm)
            set_single(2 * pos, tl, tm, x, v);
        else
            set_single(2 * pos + 1, tm + 1, tr, x, v);
    }

    void set(ll x, ll value) {
        set_single(1, 0, n, x, value);
    }

    ll query_single(ll pos, ll tl, ll tr, ll x, ll acc) {
        if (tl == tr) return vec[pos] + acc;
        ll tm = (tl + tr) / 2ll;
        acc += vec[pos];
        if (x <= tm)
            return query_single(2 * pos, tl, tm, x, acc);
        else
            return query_single(2 * pos + 1, tm + 1, tr, x, acc);
    }

    ll query(ll x) {
        return query_single(1, 0, n, x, 0);
    }
};

ll find_top(const vector<ll> &bis, const ll ai, ll low, ll high) {
    if (bis[high] < ai) return high;
    while (high - low > 1) {
        ll mid = (low + high) / 2;
        if (bis[mid] < ai)
            low = mid;
        else
            high = mid;
    }

    return low;
}

int main() {
    ll n;
    scanf("%lld\n", &n);
    // cin >> n;
    vector<ll> ais(n), pis(n);
    REP(i, n)
    scanf("%lld", &ais[i]);
    // cin >> ais[i];
    getchar();  // newline
    REP(i, n)
    scanf("%lld", &pis[i]);
    getchar();  // newline
    // cin >> pis[i];
    ll m;
    scanf("%lld\n", &m);
    // cin >> m;
    vector<ll> bis(m + 1);
    unordered_map<ll, ll> b_elems = {{LONG_LONG_MIN, 0}};
    bis[0] = LONG_LONG_MIN;
    REP(i, m) {
        scanf("%lld", &bis[i + 1]);
        b_elems.emplace(bis[i + 1], i + 1);
    }
    // cin >> bis[i];
    getchar();  // newline
    segment_tree cost(m + 1);
    ll reached = 0ll;
    REP(i, n) {
        ll ai = ais[i], pi = pis[i];
        auto it = b_elems.find(ai);
        if (it != b_elems.end()) {
            ll j = it->second, new_val;
            if (j <= reached + 1) {
                auto curr_cost = cost.query(j);
                auto prev_cost = cost.query(j - 1);
                if (j <= reached)
                    new_val = min(curr_cost + min(0ll, pis[i]), prev_cost);
                else
                    new_val = prev_cost;
            }

            ll top;
            if (pi <= 0)
                top = reached;
            else
                top = find_top(bis, ai, 0, reached);
            cost.add(0, top, pi);

            if (j <= reached + 1) {
                cost.set(j, new_val);
                if (j == reached + 1) reached++;
            }
        } else {
            ll top;
            if (pi <= 0)
                top = reached;
            else
                top = find_top(bis, ai, 0, reached);
            cost.add(0, top, pi);
        }
    }
    if (reached != m) {
        printf("NO\n");
    } else {
        printf("YES\n%lld\n", cost.query(m));
    }
}