Submission #918710

#	Time	Username	Problem	Language	Result	Execution time	Memory
918710		Tuanlinh123	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	796 ms	135836 KiB

constellation3

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=200005;
pll sp[20][maxn];
vector <ll> A[maxn];
vector <pll> Q[maxn];
ll n, m, root, sum, dp[maxn], bit[maxn];
ll Time, tin[maxn], tout[maxn], jump[20][maxn];

pll query(ll l, ll r)
{
    ll j=__lg(r-l+1);
    return max(sp[j][l], sp[j][r-(1<<j)+1]);
}

void getedge(ll l, ll r, ll rt)
{
    if (l>r) return;
    ll p=query(l, r).se;
    if (rt) A[rt].pb(p);
    else root=p;
    getedge(l, p-1, p), getedge(p+1, r, p);
}

void dfs(ll u)
{
    tin[u]=++Time;
    for (ll i=1; i<20; i++)
        jump[i][u]=jump[i-1][jump[i-1][u]];
    for (ll v:A[u])
        jump[0][v]=u, dfs(v);
    tout[u]=Time;
}

void update(ll l, ll r, ll val)
{
    for (; l<=n; l+=l&(-l)) bit[l]+=val;
    for (++r; r<=n; r+=r&(-r)) bit[r]-=val;
}

ll query(ll i)
{
    ll ans=0;
    for (; i; i-=i&(-i)) ans+=bit[i];
    return ans;
}

void dfs2(ll u)
{
    ll s=0;
    for (ll v:A[u]) dfs2(v), s+=v, dp[u]+=dp[v];
    for (ll v:A[u]) if (v!=s)
        update(tin[v], tout[v], dp[s-v]);
    for (auto [x, c]:Q[u])
    {
        c+=query(tin[x]);
        for (ll v:A[x]) c+=dp[v];
        dp[u]=max(dp[u], c);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (ll i=1; i<=n; i++)
        cin >> sp[0][i].fi, sp[0][i].se=i;
    for (ll i=1; i<20; i++)
        for (ll j=1; j+(1<<i)<=n+1; j++)
            sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
    getedge(1, n, 0), dfs(root); cin >> m;
    for (ll i=1; i<=m; i++)
    {
        ll x, y, c, p; cin >> x >> y >> c; p=x, sum+=c;
        for (ll j=19; j>=0; j--)
            if (jump[j][p] && sp[0][jump[j][p]].fi<y)
                p=jump[j][p];
        Q[p].pb({x, c});
    }
    dfs2(root);
    cout << sum-dp[root];
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:79:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   79 |             sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
      |                                                    ~^~

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