Submission #1105694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105694		vjudge1	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	328 ms	86176 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define all(x) x.begin(),x.end()
#define int long long

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

const ll maxn=2e5+69;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=1e9+7;

vector<int> L,adj[maxn];
int n,a[maxn],par[maxn],in[maxn],out[maxn],Time,up[maxn][20],dp[maxn];
vector<pii> qr[maxn];
struct fen
{
    int st[maxn];
    void Update1(int u,int w)
    {
        for(;u<=n+1;u+=u&-u) st[u]+=w;
    }
    void Update(int l,int r,int w)
    {
        Update1(r+1,-w);
        Update1(l,w);
    }
    int Get(int u)
    {
        int r=0;
        for(;u>0;u-=u&-u) r+=st[u];
        return r;
    }
}tree1,tree2;

void dfs1(int u)
{
    in[u]=++Time;
    for(int v:adj[u])
    {
        up[v][0]=u;
        for1(i,1,18) up[v][i]=up[up[v][i-1]][i-1];
        dfs1(v);
    }
    out[u]=Time;
}
void dfs(int u)
{
    for(int v: adj[u])
    {
        dfs(v);
        dp[u]+=dp[v];
    }
    tree1.Update(in[u],out[u],dp[u]);
    for(auto v:qr[u])
    {
//        if (u==3) cerr<< v.fi<<" su "<<tree1.Get(in[u],out[u])<<'\n';
        dp[u]=max(dp[u],v.se + tree1.Get(in[v.fi]) - tree2.Get(in[v.fi]));
    }
//    if (u==4) cerr<< dp[u]<<'\n';
    tree2.Update(in[u],out[u],dp[u]);
}
void sol()
{
    cin >> n;
    for1(i,1,n) cin >> a[i];
    a[0]=a[n+1]=n;
    L.pb(0);
    for1(i,1,n)
    {
        while (a[L.back()]<a[i])
        {
            if (a[par[L.back()]]>a[i]) par[L.back()]=i;
            L.pop_back();
        }
        par[i]=L.back();
        L.pb(i);
    }
//    for1(i,1,n) cerr<< par[i]<<'\n';
    for1(i,1,n)
    {
        adj[par[i]].pb(i);
//        cerr<<par[i]<<" -> "<<i<<'\n';
    }
    dfs1(0);
    int q; cin >>q;
    int rs=0;
    for1(i,1,q)
    {
        int u,h,w;
        cin >> u >>h>>w;
        rs+=w;
        int uu=u;
//        cerr<< uu<<'\n';
        for2(i,18,0) if (a[up[uu][i]] < h) uu=up[uu][i];
        qr[uu].pb({u,w});
    }
    dfs(0);
    cout << rs-dp[0];
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("990G.inp","r",stdin);
//    freopen("990G.out","w",stdout);

    int t=1;//cin >> t;
    for1(i,1,t) {
//        cout << "Case #"<<i<<": ";
        sol();
    }
}

/*
4 12
1 2 3
1 3
2 3
2 1
1 2
1 2
1 4
1 1
1 1
2 4
2 3
1 1
3 4



*/

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