Submission #1152933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152933		pokmui9909	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	724 ms	81164 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, M, A[200005], T[800005], P[22][200005], Rt = 0;
vector<ll> C[200005];
vector<pair<ll, ll>> V[200005];

void upd(ll n, ll s, ll e, ll k, ll v){
    if(s == e){
        T[n] += v; return;
    }
    ll m = (s + e) / 2;
    if(k <= m) upd(n * 2, s, m, k, v);
    else upd(n * 2 + 1, m + 1, e, k, v);
    T[n] = T[n * 2] + T[n * 2 + 1];
}
ll qry(ll n, ll s, ll e, ll l, ll r){
    if(e < l || s > r) return 0;
    if(l <= s && e <= r) return T[n];
    ll m = (s + e) / 2;
    return qry(n * 2, s, m, l, r) + qry(n * 2 + 1, m + 1, e, l, r);
}

void Construct(){
    vector<ll> L(N + 1), R(N + 1);
    for(ll i = 1; i <= N; i++){
        ll p = i - 1;
        while(A[p] > A[i]) p = P[0][p];
        L[i] = R[p], R[p] = i, P[0][L[i]] = i, P[0][i] = p;
    }
    for(ll i = 1; i <= N; i++){
        if(P[0][i] == 0){
            Rt = i;
            P[0][i] = i;
        } else {
            C[P[0][i]].push_back(i);
        }
    }
    for(ll j = 1; j < 20; j++){
        for(ll i = 1; i <= N; i++){
            P[j][i] = P[j - 1][P[j - 1][i]];
        }
    }
}

ll S[200005], In[200005], Out[200005], up[200005], dp[200005], Num = 0;

void init(ll u){
    S[u] = 1;
    for(auto v : C[u]){
        init(v); S[u] += S[v];
    }
}
void dcp(ll u){
    for(auto &v : C[u]){
        dcp(v);
        if(S[v] > S[C[u][0]]) swap(C[u][0], v);
    }
}
void hld(ll u){
    In[u] = ++Num;
    for(auto v : C[u]){
        up[v] = (v == C[u][0] ? up[u] : v);
        hld(v);
    }
    Out[u] = Num;
}

void cal(ll u){
    for(auto v : C[u]){
        cal(v);
        dp[u] += dp[v];
    }
    for(auto e : V[u]){
        ll v = e.first, c = e.second, Res = 0;
        while(up[u] != up[v]){
            Res += qry(1, 1, N, In[up[v]], In[v]);
            v = P[0][up[v]];
        }
        Res += qry(1, 1, N, In[u], In[v]);
        dp[u] = max(dp[u], Res + c);
    }
    upd(1, 1, N, In[P[0][u]], dp[u]);
    upd(1, 1, N, In[u], -dp[u]);
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N;
    for(ll i = 1; i <= N; i++){
        cin >> A[i];
        A[i] = N - A[i];
    }
    Construct();
    init(Rt); dcp(Rt); hld(Rt);
    cin >> M;
    ll Sum = 0;
    for(ll i = 1; i <= M; i++){
        ll x, y, c; cin >> x >> y >> c;
        Sum += c;
        y = N + 1 - y;
        ll u = x;
        for(ll j = 19; j >= 0; j--){
            if(A[P[j][u]] >= y) u = P[j][u];
        }
        V[u].push_back({x, c});
    }
    cal(Rt);
    cout << Sum - dp[Rt];
}

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