Submission #701026

#	Time	Username	Problem	Language	Result	Execution time	Memory
701026		ParsaS	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	375 ms	123380 KiB

constellation3

// In the name of God
// sorry M
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
#define int ll
const int N = 4e5 + 5, L = 20;
int n, m, A[N], H[N];
int id[N], sprc[N][L], ver, tin[N], tout[N], T;
set<pair<int, pair<int, int> > > st[N];
vector<int> adj[N];
ll dp[N], fen[N];

ll query(int i) {
    ll res = 0;
    for (i; i > 0; i -= i & -i)
        res += fen[i];
    return res;
}
void upd(int i, int val) {
    for (i; i < N; i += i & -i)
        fen[i] += val;
}
void range_upd(int l, int r, int val) {
    upd(l, val);
    upd(r + 1, -val);
}

void _merge(int v, int u) {
    if (st[v].size() < st[u].size())
        st[v].swap(st[u]);
    for (auto x : st[u])
        st[v].insert(x);
}

void dfs(int v, int p = 0) {
    tin[v] = ++T;
    int lc = 0, rc = 0;
    for (auto u : adj[v]) {
        dfs(u, v);
        _merge(v, u);
        if (lc == 0)
            lc = u;
        else
            rc = u;
    }
    if (rc) {
        range_upd(tin[lc], tout[lc], dp[rc]);
        range_upd(tin[rc], tout[rc], dp[lc]);
    }
    dp[v] = dp[lc] + dp[rc];
    range_upd(tin[v], tin[v], dp[v]);
    while (!st[v].empty() && st[v].begin()->fi <= H[p]) {
        dp[v] = max(dp[v], query(tin[st[v].begin()->se.fi]) + st[v].begin()->se.se);
        //cout << "rem " << v << ' ' << st[v].begin()->se.fi << ' ' << query(tin[st[v].begin()->se.fi]) << endl;
        st[v].erase(st[v].begin());
    }
    tout[v] = ++T;
    //cout << v << ' ' << dp[v] << endl;
}

int build(int l, int r) {
    if (r < l)
        return -1;
    int lg = __lg(r - l + 1);
    int v = sprc[l][lg];
    if (A[v] < A[sprc[r - (1 << lg) + 1][lg]])
        v = sprc[r - (1 << lg) + 1][lg];
    id[v] = ++ver;
    int u = ver;
    H[u] = A[v];
    int lc = build(l, v - 1);
    int rc = build(v + 1, r);
    if (lc > -1)
        adj[u].pb(lc);
    if (rc > -1)
        adj[u].pb(rc);
    return u;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = n; i >= 1; i--) {
        sprc[i][0] = i;
        for (int l = 1; l < L; l++) {
            sprc[i][l] = sprc[i][l - 1];
            if (i + (1 << (l - 1)) <= n && A[sprc[i][l]] < A[sprc[i + (1 << (l - 1))][l - 1]])
                sprc[i][l] = sprc[i + (1 << (l - 1))][l - 1];
        }
    }
    build(1, n);
    ll sum = 0;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c; cin >> x >> y >> c;
        st[id[x]].insert(mp(y, mp(id[x], c)));
        sum += c;
    }
    H[0] = 1e9 + 10;
    dfs(1);
    //cout << dp[1] << endl;
    cout << sum - dp[1];
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'll query(ll)':
constellation3.cpp:20:10: warning: statement has no effect [-Wunused-value]
   20 |     for (i; i > 0; i -= i & -i)
      |          ^
constellation3.cpp: In function 'void upd(ll, ll)':
constellation3.cpp:25:10: warning: statement has no effect [-Wunused-value]
   25 |     for (i; i < N; i += i & -i)
      |          ^

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