Submission #1270960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270960		tvgk	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	364 ms	76176 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7, inf = 1e9 + 7;

int n, h[mxN], par[mxN][25], in[mxN], out[mxN], num;
ll lazy[mxN * 4], dp[mxN];
ii tree[mxN * 4];
vector<int> w[mxN];
vector<ii> query[mxN];

void Build(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        tree[j] = {h[l], l};
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    tree[j] = max(tree[j * 2], tree[j * 2 + 1]);
}

ii Get(int u, int v, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v)
        return {0, 0};

    if (u <= l && r <= v)
        return tree[j];

    int mid = (l + r) / 2;
    return max(Get(u, v, j * 2, l, mid), Get(u, v, j * 2 + 1, mid + 1, r));
}

void BackTrack(int u, int v, int bf)
{
    if (u > v)
        return;

    int res = Get(u, v).se;
    w[bf].push_back(res);
    par[res][0] = bf;
    for (int i = 1; i <= 20; i++)
        par[res][i] = par[par[res][i - 1]][i - 1];

    BackTrack(u, res - 1, res);
    BackTrack(res + 1, v, res);
}

int LCA(int j, int v)
{
    for (int i = 20; i >= 0; i--)
    {
        if (h[par[j][i]] < v)
            j = par[j][i];
    }
    return j;
}

void Upd(int u, int v, ll val, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v)
        return;

    if (u <= l && r <= v)
    {
        lazy[j] += val;
        return;
    }

    int mid = (l + r) / 2;
    Upd(u, v, val, j * 2, l, mid);
    Upd(u, v, val, j * 2 + 1, mid + 1, r);
}

ll Get_ver(int vt, int j = 1, int l = 1, int r = n)
{
    if (l > vt || vt > r)
        return 0;

    if (l == r)
        return lazy[j];

    int mid = (l + r) / 2;
    return Get_ver(vt, j * 2, l, mid) + Get_ver(vt, j * 2 + 1, mid + 1, r) + lazy[j];
}

void DFS(int j)
{
    in[j] = ++num;
    for (int i : w[j])
    {
        DFS(i);
        dp[j] += dp[i];
    }
    out[j] = num;

    Upd(in[j], out[j], dp[j]);
    for (ii i : query[j])
        dp[j] = max(dp[j], i.se + Get_ver(in[i.fi]));
    Upd(in[j], out[j], -dp[j]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    h[0] = inf;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    Build();
    BackTrack(1, n, 0);

    int m;
    cin >> m;
    ll sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int u, v, val;
        cin >> u >> v >> val;
        query[LCA(u, v)].push_back({u, val});
        sum += val;
    }
    DFS(Get(1, n).se);
    cout << sum - dp[Get(1, n).se];
}

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