Submission #1136133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136133		Sharky	Constellation 3 (JOI20_constellation3)	C++20	0 / 100	3 ms	5184 KiB

constellation3

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

const int N = 2e5 + 5;
int n, m, a[N], ls[N << 6], rs[N << 6], lc[N], rc[N], rt[N];
int rw[N], cl[N], cost[N];
int node = 0;
int seg[N << 6], lazy[N << 6];

// i <= v: max(x <= v dp[x][j] + j <= v dp[y][j])
// all: dp[u][i] = max(dp[x][i], j <= v dp[y][j]
// pt update: dp[u][h] = max(x <= v dp[x][j] + j <= v dp[y][j]) + c (can do in O(log n)) per

// range add, range maxmerge, all assign, range maxquery

void push(int id) {
    if (!id) return;
    seg[id] += lazy[id];
    if (lazy[id]) {
        if (ls[id]) lazy[ls[id]] += lazy[id], seg[ls[id]] += lazy[id];
        if (rs[id]) lazy[rs[id]] += lazy[id], seg[rs[id]] += lazy[id];
    }
    lazy[id] = 0;
}

void insert_value(int& root, int pos, int value, int l, int r) {
    if (!root) root = ++node;
    seg[root] = max(seg[root], value);
    // debug("modified", root, l, r, value);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (pos <= mid) insert_value(ls[root], pos, value, l, mid);
    else insert_value(rs[root], pos, value, mid + 1, r);
}

void range_add_update(int root, int ql, int qr, int v, int l, int r) {
    push(root);
    if (!root || qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        lazy[root] = v;
        push(root);
        return;
    }
    int mid = (l + r) / 2;
    range_add_update(root, ql, qr, v, l, mid);
    range_add_update(root, ql, qr, v, mid + 1, r);
    seg[root] = max(seg[ls[root]], seg[rs[root]]);
}

int range_max_query(int root, int ql, int qr, int l, int r) {
    push(root);
    if (!root || qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) {
        // debug("maxed", root, l, r, seg[root]);
        return seg[root];
    }
    int mid = (l + r) / 2;
    return max(range_max_query(ls[root], ql, qr, l, mid), range_max_query(rs[root], ql, qr, mid + 1, r));
}

int merge(int root, int x, int y) {
    push(root), push(x), push(y);
    if (!x || !y) return x + y;
    if (!root) root = ++node;
    seg[root] = max(seg[x], seg[y]);
    ls[root] = merge(ls[root], ls[x], ls[y]);
    rs[root] = merge(rs[root], rs[x], rs[y]);
    return root;
}

vector<pair<int, int>> star[N];

void process(int u, int x, int y) {
    // debug(u, x, y);
    int valx = range_max_query(rt[x], 1, a[u], 1, n);
    // debug("hi");
    int valy = range_max_query(rt[y], 1, a[u], 1, n);
    // debug("hi");
    range_add_update(rt[x], 1, n, valy, 1, n);
    // debug("hi");
    range_add_update(rt[y], 1, n, valx, 1, n);
    // debug()
    // for (auto& [r, c] : star[u]) insert_value(rt[u], r, c, 1, n);
    // debug("hi");
    rt[u] = merge(rt[u], rt[x], rt[y]);
    // for (int i = 1; i <= n; i++) {
        // debug("heya!");
        // debug(range_max_query(rt[u], i, i, 1, n));
    // }
    // debug("hi");
    for (auto& [r, c] : star[u]) {
        // debug("insert", u, r, c);
        insert_value(rt[u], r, valx + valy + c, 1, n);
    }
}

void solve() {
    int sum = 0;
    cin >> n;
    vector<int> idx;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        idx.push_back(i);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> rw[i] >> cl[i] >> cost[i];
        star[rw[i]].push_back({cl[i], cost[i]});
        sum += cost[i];
    }
    sort(idx.begin(), idx.end(), [&] (int x, int y) { return make_pair(a[x], x) < make_pair(a[y], y); });
    stack<pair<int, int>> st;
    vector<int> lst(n+1, -1), nxt(n+1, -1);
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && st.top() < make_pair(a[i], i)) st.pop();
        if (!st.empty()) lst[i] = st.top().second;
        st.push({a[i], i});
    }
    while (!st.empty()) st.pop();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && st.top() < make_pair(a[i], i)) st.pop();
        if (!st.empty()) nxt[i] = st.top().second;
        st.push({a[i], i});
    }
    for (int i = 1; i <= n; i++) {
        if (lst[i] == -1) lc[nxt[i]] = i;
        else if (nxt[i] == -1) rc[lst[i]] = i;
        else if (make_pair(a[lst[i]], lst[i]) < make_pair(a[nxt[i]], nxt[i])) rc[lst[i]] = i;
        else lc[nxt[i]] = i;
    }
    for (auto i : idx) process(i, lc[i], rc[i]);
    // debug(idx);
    // for (int i = 1; i <= n; i++) debug(i, lc[i], rc[i]);
    cout << sum - range_max_query(rt[idx.back()], 1, n, 1, n) << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

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