Submission #1079881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079881		_callmelucian	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	246 ms	35336 KiB

constellation3

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;

struct item {
    int core, height, lb, rb, value;

    item() : core(0), height(0), lb(0), rb(0), value(0) {}

    item (int l, int r) :
        core(0), height(0), lb(l), rb(r), value(0) {}

    item (int c, int h, int l, int r, int v) :
        core(c), height(h), lb(l), rb(r), value(v) {}

    bool operator < (const item &o) const {
        if (rb == o.rb) return lb > o.lb;
        return rb < o.rb;
    }

    friend istream& operator >> (istream &inp, item &cur) {
        inp >> cur.core >> cur.height >> cur.value;
        return inp;
    }
} star[mn];

struct IT {
    vector<int> lazy;
    IT (int sz) : lazy(4 * sz, INT_MAX) {}

    void update (int a, int b, int val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            lazy[k] = min(lazy[k], val);
            return;
        }
        int mid = (l + r) >> 1;
        update(a, b, val, 2 * k, l, mid);
        update(a, b, val, 2 * k + 1, mid + 1, r);
    }

    int query (int pos, int k, int l, int r) {
        int ans = lazy[k], mid = (l + r) >> 1;
        if (l == r) return ans;
        if (l <= pos && pos <= mid)
            return min(ans, query(pos, 2 * k, l, mid));
        return min(ans, query(pos, 2 * k + 1, mid + 1, r));
    }
} tree(mn);

struct DSU {
    vector<ll> par, weight;
    DSU (int sz) : par(sz + 1), weight(sz + 1) {}

    pl get (int u) {
        if (!par[u]) return {u, weight[u]};
        pl cur = get(par[u]);
        weight[u] += cur.second - weight[cur.first];
        par[u] = cur.first;
        return {par[u], weight[u] + weight[par[u]]};
    }

    void unite (int p, int u) {
        p = get(p).first, u = get(u).first;
        if (p != u) par[u] = p;
    }

    void incr (int u, ll val) { weight[u] += val; }
};

vector<int> pos[mn];
ll dp[mn], sumTree[mn];
int a[mn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int m; cin >> m; ll sum = 0;
    for (int i = 1; i <= m; i++) {
        cin >> star[i];
        sum += star[i].value;
        pos[star[i].core].push_back(i);
    }

    // construct lb
    vector<pii> line; line.emplace_back(INT_MAX, 0);
    for (int i = 1; i <= n; i++) {
        while (line.back().first <= a[i]) line.pop_back();
        line.emplace_back(a[i], i);

        for (int u : pos[i]) {
            auto it = lower_bound(all(line), make_pair(star[u].height, 0), greater<pii>());
            star[u].lb = prev(it)->second + 1;
        }
    }

    // construct rb
    line.clear(); line.emplace_back(INT_MAX, n + 1);
    for (int i = n; i >= 1; i--) {
        while (line.back().first <= a[i]) line.pop_back();
        line.emplace_back(a[i], i);

        for (int u : pos[i]) {
            auto it = lower_bound(all(line), make_pair(star[u].height, 0), greater<pii>());
            star[u].rb = prev(it)->second - 1;
        }
    }
    sort(star + 1, star + 1 + m);

    // sweep ranges
    vector<int> roots; IT tree(n);
    DSU dsuDP(m), dsuSum(m);

    for (int i = 1; i <= m; i++) {
        while (roots.size() && star[i].lb <= star[roots.back()].lb) {
            // i is the new parent of roots.back()
            sumTree[i] += dp[roots.back()], dsuDP.unite(i, roots.back()), dsuSum.unite(i, roots.back());
            roots.pop_back();
        }
        roots.push_back(i);
        dsuSum.incr(i, sumTree[i]);
        tree.update(star[i].lb, star[i].rb, i, 1, 1, n);

        int j = tree.query(star[i].core, 1, 1, n);
        dp[i] = max(sumTree[i], dsuSum.get(j).second - dsuDP.get(j).second + star[i].value);
        dsuDP.incr(i, dp[i]);
    }

    ll ans = 0;
    for (int u : roots) ans += dp[u];
    cout << sum - ans;

    return 0;
}

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