Submission #851872

#	Time	Username	Problem	Language	Result	Execution time	Memory
851872		danikoynov	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	347 ms	68688 KiB

constellation3

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

struct point
{
    int x, y;
    ll c;
};

bool cmp(point p1, point p2)
{
    return p1.y < p2.y;
}

point star[maxn];
int n, m, a[maxn];
vector < pair < int, ll > > loc_star[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    cin >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> star[i].x >> star[i].y >> star[i].c;
        loc_star[star[i].x].push_back({star[i].y, star[i].c});
    }

    ///sort(star + 1, star + m + 1, cmp);
}

int lc[maxn], rc[maxn], par[maxn];
int cartesian_tree()
{
    for (int i = 1; i <= n; i ++)
    {
        lc[i] = rc[i] = -1;
        par[i] = 0;
    }

    stack < int > st;
    int root = -1;
    for (int i = 1; i <= n; i ++)
    {
        while(!st.empty() && a[st.top()] < a[i])
        {
            lc[i] = st.top();
            st.pop();
        }

        if (st.empty())
            root = i;
        else
        {
            par[i] = st.top();
            rc[st.top()] = i;
        }

        if (lc[i] != -1)
            par[lc[i]] = i;

        st.push(i);
    }

    return root;
    /**cout << "cartesian" << endl;

    for (int i = 1; i <= n; i ++)
        cout << i << " " << lc[i] << " " << rc[i] << endl;*/

}

const int maxlog = 21;

int tin[maxn], tout[maxn], timer;
int jump[maxlog][maxn];

vector < pair < int, ll > > links[maxn];
void create_links(int v)
{
    jump[0][v] = par[v];
    for (int j = 1; j < maxlog; j ++)
        jump[j][v] = jump[j - 1][jump[j - 1][v]];

    for (pair < int, ll > cur : loc_star[v])
    {
        int to = v;
        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (jump[bit][to] == 0)
                continue;
            if (a[jump[bit][to]] < cur.first)
                to = jump[bit][to];
        }

        links[to].push_back({v, cur.second});
    }

    tin[v] = ++ timer;
    if (lc[v] != -1)
        create_links(lc[v]);
    if (rc[v] != -1)
        create_links(rc[v]);
    tout[v] = timer;
}

struct bit
{
    ll fen[maxn];

    void update(int v, ll val)
    {
        for (int i = v; i < maxn; i += (i & -i))
            fen[i] += val;
    }

    ll query(int v)
    {
        ll sum = 0;
        for (int i = v; i > 0; i -= (i & -i))
            sum += fen[i];
        return sum;
    }

    void range_update(int l, int r, ll val)
    {
        update(l, val);
        update(r + 1, - val);
    }
};

bit tree_above, tree_under;

ll dp[maxn];
void dfs(int v)
{

    ll sum_dp = 0;
    if (lc[v] != -1)
    {
        dfs(lc[v]);
        sum_dp += dp[lc[v]];
    }
    if (rc[v] != -1)
    {
        dfs(rc[v]);
        sum_dp += dp[rc[v]];
    }

    dp[v] = sum_dp;
    tree_under.range_update(tin[v], tout[v], sum_dp);

    for (pair < int, ll > cur : links[v])
    {
        //cout << v << " : " << cur.first << " : " << cur.second << endl;
        dp[v] = max(dp[v], cur.second + tree_under.query(tin[cur.first]) - tree_above.query(tin[cur.first]));
    }
    //cout << "vertex " << v << " " << dp[v] << endl;
    tree_above.range_update(tin[v], tout[v], dp[v]);
}
void solve()
{
    input();
    int root = cartesian_tree();
    create_links(root);
    dfs(root);
    /// remember to subtract
    ll ans = 0;
    for (int i = 1; i <= m; i ++)
        ans += star[i].c;
    ans -= dp[root];
    cout << ans << endl;
}

int main()
{
    speed();
    solve();
    return 0;
}

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