Submission #1270920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270920		windowwife	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	452 ms	45244 KiB

constellation3

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, LG = 20, inf = 1e9;
int n, q, a[maxn], st[LG][maxn], l[maxn], r[maxn], t, tin[maxn], tout[maxn], m, x[maxn], y[maxn], c[maxn];
ll fw[maxn], dp[maxn], sum = 0;
vector<int> stars[maxn];
void upd (int x, ll val)
{
    for (; x <= n; x += (x & (-x)))
        fw[x] += val;
}
ll get (int x)
{
    ll res = 0;
    for (; x > 0; x -= (x & (-x)))
        res += fw[x];
    return res;
}
void dfs (int u)
{
    tin[u] = ++t;
    if (l[u] != -1)
    {
        dfs(l[u]);
        dp[u] += dp[l[u]];
    }
    if (r[u] != -1)
    {
        dfs(r[u]);
        dp[u] += dp[r[u]];
    }
    if (l[u] != -1 && r[u] != -1)
    {
        upd(tin[l[u]], dp[r[u]]);
        upd(tout[l[u]] + 1, -dp[r[u]]);
        upd(tin[r[u]], dp[l[u]]);
        upd(tout[r[u]] + 1, -dp[l[u]]);
    }
    for (int i : stars[u])
    {
        //cout << "stars " << i << " " << x[i] << " " << u << '\n';
        ll tmp = get(tin[x[i]]) + c[i];
        if (l[x[i]] != -1) tmp += dp[l[x[i]]];
        if (r[x[i]] != -1) tmp += dp[r[x[i]]];
        dp[u] = max(dp[u], tmp);
    }
    tout[u] = t;
    //cout << u << " " << dp[u] << '\n';
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    a[0] = inf;
    l[0] = r[0] = -1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        l[i] = r[i] = -1;
        int j = i - 1;
        while (a[j] < a[i]) j = st[0][j];
        int k = r[j];
        st[0][i] = j;
        r[j] = i;
        if (k != -1)
        {
            st[0][k] = i;
            l[i] = k;
        }
    }
    for (int j = 1; j < LG; j++)
        for (int i = 1; i <= n; i++)
            st[j][i] = st[j - 1][st[j - 1][i]];
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> x[i] >> y[i] >> c[i];
        int u = x[i];
        for (int j = LG - 1; j >= 0; j--)
            if (st[j][u] != 0 && a[st[j][u]] < y[i])
            {
                u = st[j][u];
            }
        stars[u].push_back(i);
        sum += c[i];
    }
    dfs(r[0]);
    cout << sum - dp[r[0]];
}

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