Submission #921341

#	Time	Username	Problem	Language	Result	Execution time	Memory
921341		hotboy2703	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	568 ms	109668 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1LL)
const ll MAXN = 2e5;
const ll MAXK = 18;
ll n,m;
ll a[MAXN + 1];
namespace max_height{
    ll sp[MAXK][MAXN+1];
    ll best(ll x,ll y){
        if (a[x]>a[y])return x;
        return y;
    }
    void init(){
        for (ll i = 1;i <= n; i++){
            sp[0][i] = i;
        }
        for (ll j = 1;j < MAXK;j ++){
            for (ll i = 1;i + MASK(j) - 1 <= n;i ++){
                sp[j][i] = best(sp[j-1][i],sp[j-1][i+MASK(j-1)]);
            }
        }
    }
    ll query(ll l,ll r){
        ll sz = __lg(r-l+1);
        return best(sp[sz][l],sp[sz][r-MASK(sz)+1]);
    }
}
struct star{
    ll x,y,c;
};
star b[MAXN + 1];
vector <ll> g[MAXN + 1];
ll pre[MAXK][MAXN + 1];
void add_edge(ll p,ll u){
    g[p].push_back(u);
    pre[0][u] = p;
}
ll build_tree(ll l,ll r){
//    cout<<l<<' '<<r<<'\n';
    ll mid = max_height::query(l,r);
    if (l <= mid - 1)add_edge(mid,build_tree(l,mid-1));
    if (mid + 1 <= r)add_edge(mid,build_tree(mid+1,r));
    return mid;
}
vector <pll> path[MAXN+1];
ll dp[MAXN+1];
ll in[MAXN+1],out[MAXN+1];
ll timeDFS;
ll BIT[MAXN+1];
void update(ll i,ll x){
    for (;i <= n;i += i & -i)BIT[i]+=x;
}
void update(ll l,ll r,ll x){
    update(l,x);
    update(r+1,-x);
}
ll get(ll i){
    ll res = 0;
    for (;i > 0;i -= i & -i)res += BIT[i];
    return res;
}
void dfs(ll u){
    in[u] = ++timeDFS;
    for (auto v:g[u]){
        dfs(v);
    }
    out[u] = timeDFS;
}
void solve(ll u){
    for (auto v:g[u]){solve(v);dp[u] += dp[v];update(in[u],in[u],dp[v]);}
    if (sz(g[u])==2){
        ll v1,v2;
        v1 = g[u][0];
        v2 = g[u][1];
        update(in[v1],out[v1],dp[v2]);
        update(in[v2],out[v2],dp[v1]);
    }
    for (auto x:path[u]){
        dp[u] = max(dp[u],x.se+get(in[x.fi]));
    }
//    cout<<"DP "<<u<<' '<<dp[u]<<'\n';
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for (ll i = 1;i <= n;i ++)cin>>a[i];
    cin>>m;
    ll sum = 0;
    for (ll i = 1;i <= m;i ++){
        cin>>b[i].x>>b[i].y>>b[i].c;
        sum += b[i].c;
    }
    max_height::init();
    ll root = build_tree(1,n);
    for (ll i = 1;i < MAXK;i ++){
        for (ll u = 1;u <= n;u ++){
            pre[i][u] = pre[i-1][pre[i-1][u]];
        }
    }
//    for (ll i = 1;i <= n; i++){
//        cout<<pre[0][i]<<' '<<pre[1][i]<<' '<<pre[2][i]<<'\n';
//    }
//    cout<<"END\n";
    a[0] = n;
    for (ll i = 1;i <= m;i ++){
        ll p = b[i].x;
        for (ll j = MAXK-1;j>=0;j--){
            if (a[pre[j][p]] < b[i].y){
                p = pre[j][p];
            }
        }
//        cout<<p<<' '<<b[i].x<<' '<<b[i].c<<'\n';
        path[p].push_back({b[i].x,b[i].c});
    }
    dfs(root);
    solve(root);
    cout<<sum-dp[root];
    return 0;
}

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