Submission #212740

#	Time	Username	Problem	Language	Result	Execution time	Memory
212740		Alexa2001	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	408 ms	63224 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

typedef long long ll;
const ll inf = 1e18;

int i, root, L[Nmax], R[Nmax], t[Nmax], H[Nmax];
multiset<pair<int,ll>> v[Nmax];

ll lazy[Nmax];

int n, m;



void cartesian_tree()
{
    int i;

    t[1] = 0; root = 1;
    for(i=2; i<=n; ++i)
    {
        int node = i-1;
        while(t[node] && H[node] < H[i])
            node = t[node];

        if(H[node] >= H[i])
        {
            if(R[node])
            {
                L[i] = R[node];
                t[L[i]] = i;
            }

            R[node] = i;
            t[i] = node;
        }
        else
        {
            root = i;
            L[i] = node;
            t[i] = 0;
            t[node] = i;
        }
    }
}

void Merge(int node, int son, int H)
{
    /*
    cerr << "#\n";
    for(auto it : v[node]) cerr << it.first << ' ' << it.second << endl;
    cerr << "#\n";
    for(auto it : v[son]) cerr << it.first << ' ' << it.second << endl;
    cerr << "#\n";
    */

    ll val1 = inf, val2 = inf;
    while(v[son].size() && v[son].begin()->first <= H)
    {
        val1 = min(val1, v[son].begin()->second + lazy[son]);
        v[son].erase(v[son].begin());
    }

    while(v[node].size() && v[node].begin()->first <= H)
    {
        val2 = min(val2, v[node].begin()->second + lazy[node]);
        v[node].erase(v[node].begin());
    }

    if(v[node].size() < v[son].size())
    {
        swap(v[node], v[son]);
        swap(lazy[node], lazy[son]);
        swap(val1, val2);
    }

    assert(val1 != inf && val2 != inf);
    if(val1 == inf)
    {
        v[node].insert({0, val2 - lazy[node]});
        return;
    }

    lazy[node] += val1;
    for(auto it : v[son])
        v[node].insert({it.first, it.second + lazy[son] - lazy[node] + val2});

    v[node].insert({0, val1 + val2 - lazy[node]});

   // for(auto it : v[node]) cerr << it.first << ' ' << it.second + lazy[node] << endl;
}

void solve(int node)
{
    int son1 = L[node], son2 = R[node];
    if(!son1 && !son2) return;

    if(son1) solve(son1);
    if(son2) solve(son2);

    if(son1) Merge(node, son1, H[node]);
    if(son2) Merge(node, son2, H[node]);
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n;

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

    cartesian_tree();

    cin >> m;
    for(i=1; i<=m; ++i)
    {
        int x, y, cost;
        cin >> x >> y >> cost;
        v[x].insert({y, cost});
    }

    for(i=1; i<=n; ++i)
    {
        ll sum = 0;
        for(auto it : v[i])
            sum += it.second;

        multiset<pair<int, ll>> S;
        for(auto it : v[i])
            S.insert({it.first, sum - it.second});

        S.insert({0, sum});

        swap(S, v[i]);
        lazy[i] = 0;
    }

    solve(root);

    ll ans = inf;
    for(auto it : v[root])
        ans = min(ans, it.second);
    cout << ans + lazy[root] << '\n';

    return 0;
}

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