Submission #1102435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102435		12345678	Constellation 3 (JOI20_constellation3)	C++17	0 / 100	3 ms	19024 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, m, h[nx], x, y, c, sm, l[nx], r[nx], rt, res, lz[nx];
vector<pair<ll, ll>> d[nx];
set<pair<ll, ll>> dp[nx];
stack<ll> s;

void add(int idx, pair<ll, ll> vl)
{
    auto itr=dp[idx].lower_bound(make_pair(vl.first, LLONG_MIN));
    if (itr->first==vl.first) vl.second=max(vl.second, itr->second), dp[idx].erase(itr);
    itr=dp[idx].lower_bound(make_pair(vl.first, LLONG_MIN));
    if (itr!=dp[idx].begin()&&prev(itr)->second>=vl.second) return;
    while (itr!=dp[idx].end()&&itr->second<=vl.second) itr=dp[idx].erase(itr);
    dp[idx].insert(vl);
}

void show(int idx)
{
    cout<<"show "<<idx<<'\n';
    for (auto [x, y]:dp[idx]) cout<<x<<' '<<y+lz[idx]<<'\n';
}

void solve(int u)
{
    if (l[u]) solve(l[u]);
    if (r[u]) solve(r[u]);
    ll vl=0, vr=0;
    if (l[u]||r[u])
    { 
        if (!l[u]) swap(l[u], r[u]);
        if (dp[l[u]].size()<dp[r[u]].size()) swap(l[u], r[u]);
        while (!dp[l[u]].empty()&&dp[l[u]].begin()->first<=h[u]) vl=dp[l[u]].begin()->second+lz[l[u]], dp[l[u]].erase(dp[l[u]].begin());
        while (!dp[r[u]].empty()&&dp[r[u]].begin()->first<=h[u]) vr=dp[r[u]].begin()->second+lz[r[u]], dp[r[u]].erase(dp[r[u]].begin());
        //cout<<"debug "<<u<<' '<<vl<<' '<<vr<<'\n';
        //cout<<"l "<<u<<' '<<l[u]<<' '<<r[u]<<'\n';
        swap(dp[l[u]], dp[u]);
        lz[u]=lz[l[u]];
        lz[u]+=vr;
        add(u, {h[u], vl+vr-lz[u]});
        for (auto [y, c]:dp[r[u]]) add(u, {y, c+lz[r[u]]-lz[u]});
    }
    for (auto [y, c]:d[u]) add(u, {y, c+vl+vr-lz[u]});
    //show(u);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>h[i];
    cin>>m;
    for (int i=1; i<=m; i++) cin>>x>>y>>c, d[x].push_back({y, c}), sm+=c;
    for (int i=1; i<=n; i++)
    {
        while (!s.empty()&&h[s.top()]<h[i]) l[i]=s.top(), s.pop();
        if (!s.empty()) r[s.top()]=i;
        else rt=i;
        s.push(i);
    }
    solve(rt);
    //cout<<"here "<<rt<<' '<<prev(dp[rt].end())->second<<'\n';
    if (dp[rt].empty()) cout<<sm;
    else cout<<sm-(prev(dp[rt].end())->second+lz[rt]);
}

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