Submission #366673

#	Time	Username	Problem	Language	Result	Execution time	Memory
366673		12tqian	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	1222 ms	96080 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int) (x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 1e9;

struct IntervalUnion {
    std::set<std::pair<int, int>> le, ri;

    void reset() {
        le.clear();
        ri.clear();
    }

    // inserts an interval while returning the intervals it intersected with
    std::vector<std::pair<int, int>> insert(std::pair<int, int> x) {
        std::set<std::pair<int, int>> bad;
        std::vector<std::pair<int, int>> ret;
        std::pair<int, int> use1 = std::make_pair(x.first, -INF), use2 = std::make_pair(x.second, INF);
        auto it1 = le.lower_bound(use1);
        auto it2 = ri.lower_bound(use2);
        if (it2 != ri.end()) {
            int lo = (*it2).second, hi = (*it2).first;
            if (lo <= x.first && x.second <= hi) {
                ret.emplace_back(std::make_pair(lo, hi));
                int mn = x.first, mx = x.second;
                for (auto b: ret) {
                    le.erase(b); ri.erase(std::make_pair(b.second, b.first));
                    mn = std::min(mn, b.first); mx = std::max(mx, b.second);
                }
                le.insert(std::make_pair(mn, mx)); ri.insert(std::make_pair(mx, mn));
                return ret;
            }
        }
        if (it1 != le.end()) {
            while (it1 != le.end()) {
                auto val = (*it1);
                if (val.first <= x.second) bad.insert(val);
                else break;
                it1 = next(it1);
            }
        }
        if (it2 != ri.begin()) {
            it2 = prev(it2);
            while (true) {
                auto val = (*it2);
                if (val.first >= x.first) bad.insert(std::make_pair(val.second, val.first));
                else break;
                if (it2 == ri.begin()) break;
                it2 = prev(it2);
            }
        }
        for (auto b: bad) ret.emplace_back(b);
        int mn = x.first, mx = x.second;
        for (auto b: ret) {
            le.erase(b); ri.erase(std::make_pair(b.second, b.first));
            mn = std::min(mn, b.first); mx = std::max(mx, b.second);
        }
        le.insert(std::make_pair(mn, mx)); ri.insert(std::make_pair(mx, mn));
        return ret;
    }
};

template <class T> struct SparseTable {
    std::vector<T> v;
    std::vector<std::vector<int>> jump;

    int level(int x) { return 31 - __builtin_clz(x); }

    int comb(int a, int b) {
        return v[a] == v[b] ? std::min(a, b) : (v[a] > v[b] ? a : b);
    }

    void init(const std::vector<T>& _v) {
        v = _v;
        jump = {std::vector<int>((int) v.size())};
        iota(jump[0].begin(), jump[0].end(), 0);
        for (int j = 1; (1 << j) <= (int) v.size(); j++) {
            jump.push_back(std::vector<int>((int) v.size() - (1 << j) + 1));
            for (int i = 0; i < (int) jump[j].size(); i++) {
                jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    int index(int l, int r) {
        assert(l <= r);
        int d = level(r - l + 1);
        return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
    }

    T query(int l, int r) {
        return v[index(l, r)];
    }
};


template <class T> struct LazySeg {
    std::vector<T> sum, lazy;
    int sz;

    void init(int sz_) {
        sz = 1;
        while (sz < sz_) sz *= 2;
        sum.assign(2 * sz, 0);
        lazy.assign(2 * sz, 0);
    }

    void push(int ind, int L, int R) {
        sum[ind] += (R - L + 1) * lazy[ind];
        if (L != R) {
            lazy[2 * ind] += lazy[ind];
            lazy[2 * ind + 1] += lazy[ind];
        }
        lazy[ind] = 0;
    }

    void pull(int ind) {
        sum[ind] = sum[2 * ind] + sum[2 * ind + 1];
    }

    void build() {
        for (int i = sz - 1; i >= 1; i--) {
            pull(i);
        }
    }

    void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (hi < L || R < lo) return ;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind, L, R);
            return;
        }
        int M = (L + R) / 2;
        upd(lo, hi, inc, 2 * ind, L, M);
        upd(lo, hi, inc, 2 * ind + 1, M + 1, R);
        pull(ind);
    }

    T qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (lo > R || L > hi) return 0;
        if (lo <= L && R <= hi) return sum[ind];
        int M = (L + R) / 2;
        return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
    }
};

const bool VALUES_IN_VERTICES = true;

template <class T> class HeavyLight {
    std::vector<int> parent, heavy, depth, root, tree_pos;
    int ti = 0;
    vpi ranges;
    LazySeg<T> tree;
    LazySeg<T> subtree;

    template <class G> int dfs(const G& graph, int v) {
        int size = 1, max_subtree = 0;
        ranges[v].f = ti++;
        for (int u : graph[v]) if (u != parent[v]) {
            parent[u] = v;
            depth[u] = depth[v] + 1;
            int subtree = dfs(graph, u);
            if (subtree > max_subtree) heavy[v] = u, max_subtree = subtree;
            size += subtree;
        }
        ranges[v].s = ti - 1;
        return size;
    }

    template <class B> void process_path(int u, int v, B op) {
        for (; root[u] != root[v]; v = parent[root[v]]) {
            if (depth[root[u]] > depth[root[v]]) std::swap(u, v);
            op(tree_pos[root[v]], tree_pos[v]);
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        op(tree_pos[u] + (VALUES_IN_VERTICES ? 0 : 1), tree_pos[v]);
    }

public:
    template <class G>
    void init(const G& graph, vi roots) {
        int n = (int) graph.size();
        heavy.assign(n, -1);
        parent.assign(n, 0);
        depth.assign(n, 0);
        root.assign(n, 0);
        tree_pos.assign(n, 0);
        ranges.resize(n);
        tree.init(n);
        subtree.init(n);
        each(r, roots) {
            parent[r] = -1;
            depth[r] = 0;
            dfs(graph, r);
        }   
        for (int i = 0, current_pos = 0; i < n; ++i)
            if (parent[i] == -1 || heavy[parent[i]] != i)
            for (int j = i; j != -1; j = heavy[j]) {
                root[j] = i;
                tree_pos[j] = current_pos++;
            }
    }

    void modify_path(int u, int v, const T& value) {
        process_path(u, v, [this, &value](int l, int r) { tree.upd(l, r, value); });
    }

    T query_path(int u, int v) {
        T res = 0;
        process_path(u, v, [this, &res](int l, int r) { res += tree.qsum(l, r); });
        return res;
    }
};

template <class T> struct RangeSetSeg {
    const T UNUSED = -1;
    std::vector<T> sum, lazy;
    int sz;

    // lazy stores what to set to
    void init(int sz_) {
        sz = 1;
        while (sz < sz_) sz *= 2;
        sum.assign(2 * sz, 0);
        lazy.assign(2 * sz, UNUSED);
    }

    void push(int ind, int L, int R) {
        if (L != R) {
            if(lazy[ind] != UNUSED){
                for(int i = 0; i < 2; i++){
                    lazy[2 * ind + i] = lazy[ind];
                }
            }
        }
        if (lazy[ind] != UNUSED) sum[ind] = (R - L + 1) * lazy[ind];
        lazy[ind] = UNUSED;
    }

    void pull(int ind) { sum[ind] = sum[2 * ind] + sum[2 * ind + 1]; }

    void range_set(int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind, L, R); return;
        }
        int M = (L + R) / 2;
        range_set(lo, hi, inc, 2 * ind, L, M); range_set(lo, hi, inc, 2 * ind + 1, M + 1, R);
        pull(ind);
    }

    T qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R); if (lo > R || L > hi) return 0;
        if (lo <= L && R <= hi) return sum[ind];
        int M = (L + R) / 2;
        return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n;
    vi a(n);
    f0r(i, n) cin >> a[i], a[i]--;
    SparseTable<int> ST;
    ST.init(a);
    cin >> m;
    vector<array<int, 4>> ivals;
    f0r(i, m) {
        int x, y, c; 
        cin >> x >> y >> c;
        x--;
        y--;
        int L, R;
        int lo = 0;
        int hi = x;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (ST.query(mid, x) < y) hi = mid;
            else lo = mid + 1;
        }
        if (ST.query(lo, x) < y) L = lo;
        else L = hi;
        lo = x;
        hi = n - 1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (ST.query(x, mid) < y) lo = mid;
            else hi = mid - 1;
        }
        if (ST.query(x, hi) < y) R = hi;
        else R = lo;
        ivals.pb({L, R, c, x});
        // cout << L << " IVAL " << R << endl;
    }
    IntervalUnion IU;
    vector<pi> nodes;
    f0r(i, m) {
        nodes.pb({ivals[i][0], ivals[i][1]});
    }
    sort(all(nodes));
    nodes.erase(unique(all(nodes)), nodes.end());
    int sz = sz(nodes);
    vector<vi> in(sz), out(sz), g(sz);
    vl c(m);
    f0r(i, m) {
        c[i] = ivals[i][2];
    }
    sort(all(ivals), [](array<int, 4> a, array<int, 4> b) {
        return a[1] - a[0] < b[1] - b[0];
    });
    auto get_pos = [&](pi x) {
        return lower_bound(all(nodes), x) - nodes.begin();
    };
    // cout << "EDGE -------------------" << endl;
    f0r(i, m) {
        int l = ivals[i][0];
        int r = ivals[i][1];
        auto res = IU.insert({l, r});
        int oi = get_pos({l, r});
        each(ii, res) {
            int ni = get_pos(ii);
            if (ni == oi) continue;
            out[oi].pb(ni);
            in[ni].pb(oi);
            // cout << oi << " " << ni << endl;
            g[oi].pb(ni);
            g[ni].pb(oi);
        }
    }
    // cout << "---------------" << endl;
    vector<vpi> tags(sz); // pair of bad, cost

    f0r(i, m) { 
        int id = get_pos({ivals[i][0], ivals[i][1]});
        tags[id].eb(ivals[i][3], ivals[i][2]);
    }
    vi roots;
    f0r(i, sz) {
        if (sz(in[i]) == 0) {
            roots.pb(i);
        }
        // cout << i << " IN: ";
        // each(x, in[i]) cout << x << " ";
        // cout << endl;
        // cout << i << " OUT: ";
        // each(x, out[i]) cout << x << " ";
        // cout << endl;
        // cout << "---------------" << endl;
    }
    HeavyLight<ll> H, P;
    H.init(g, roots);
    P.init(g, roots);
    vi rev(n);
    RangeSetSeg<int> range_seg;
    range_seg.init(n);
    // f0r(i, sz(nodes)) {
    //     cout << i << ": " << nodes[i].f << " " << nodes[i].s << " NODE" << endl;
    // }
    vi par(sz);
    function<void(int)> dfs_tags = [&](int u) {
        range_seg.range_set(nodes[u].f, nodes[u].s, u);
        each(v, out[u]) {
            dfs_tags(v);
            par[v] = u;
        }
    };
    each(r, roots) {
        par[r] = -1;
        dfs_tags(r);
    }
    f0r(i, n) {
        rev[i] = range_seg.qsum(i, i);
    }

    f0r(i, sz) {
        // cout << i <<  ": ";
        each(tag, tags[i]) {
            tag.f = rev[tag.f];
            // cout << tag.f << " " << tag.s << endl;
        }
        // cout << "-----------" << endl;
    }
    vl dp(sz);
    function<void(int)> dfs = [&](int u) {
        ll best = 0;
        each(v, out[u]) {
            dfs(v);
            best += H.query_path(v, v);
        }
        each(tag, tags[u]) {
            int bad = tag.f;
            int cost = tag.s;
            // cout << u << " " << bad << " " << sz << endl;
            ll val = P.query_path(u, bad);            
            // if (u == 0 && cost == 8) {
            //     cout << val <<" VAL " << endl;
            // }
            if (u != bad) {
                val -= (H.query_path(u, bad) - dp[u]);
            }
            val += cost;
            ckmax(best, val);
        }

        dp[u] = best;
        // cout << "DP: " << u << " " << best << endl;
        H.modify_path(u, u, best);
        if (par[u] != -1) P.modify_path(par[u], par[u], best);
    };
    ll res = 0;
    each(r, roots) {
        dfs(r);
        res += dp[r];
        // cout << dp[r] << " HUUH" << endl;
    }
    ll ans = 0;
    each(e, c) ans += e;
    ans -= res;
    cout << ans << '\n';
    return 0;
}

/**
 * Each star has an interval
 * intervals can't partial intersect, must fully contain
 * you want no intersecting intervals
 * min cost to make no intersecting intervals
 * each interval has a cost
 * each interval is like in a tree structure right
 * 
 */

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65