Submission #1335933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335933		Andrey	Constellation 3 (JOI20_constellation3)	C++20	Compilation error	0 ms	0 KiB

constellation3

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

vector<long long> h(200001);
vector<pair<long long,long long>> seg(800001);
vector<long long> tree[300001];
vector<long long> pos(200001);
vector<long long> banana(200001);
vector<pair<long long,long long>> star[200001];
vector<long long> st(200001);
long long lift[200001][18];
long long br = 1;
long long n;
vector<long long> fan(400001);
vector<long long> dp(200001);

void upd(long long a, long long c) {
    while(a < fan.size()) {
        fan[a]+=c;
        a+=(a&(-a));
    }
}

long long orange(long long a) {
    long long sb = 0,c = 0;
    for(long long i = 18; i >= 0; i--) {
        if(c+(1 << i) <= a) {
            c+=(1 << i);
            sb+=fan[c];
        }
    }
    return sb;
}

void build(long long l, long long r, long long x) {
    if(l == r) {
        seg[x] = {h[l],-l};
        return;
    }
    long long mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    seg[x] = max(seg[x*2],seg[x*2+1]);
}

pair<long long,long long> calc(long long l, long long r, long long ql, long long qr, long long x) {
    if(l >= ql && r <= qr) {
        return seg[x];
    }
    if(r < ql || l > qr) {
        return {0,0};
    }
    long long mid = (l+r)/2;
    return max(calc(l,mid,ql,qr,x*2),calc(mid+1,r,ql,qr,x*2+1));
}

void dekart(long long l, long long r, long long d, long long x) {
    st[x] = 1;
    banana[x] = d;
    if(l == r) {
        pos[l] = x;
        return;
    }
    long long c = calc(1,n,l,r,1).first;
    long long y = l;
    while(true) {
        pair<long long,long long> z = calc(1,n,y,r,1);
        if(z.first != c) {
            break;
        }
        pos[-z.second] = x;
        if(y <= -z.second-1) {
            br++;
            tree[x].push_back(br);
            lift[br][0] = x;
            int w = br;
            dekart(y,(-z.second)-1,c,br);
            st[x]+=st[w];
        }
        y = -z.second+1;
    }
    if(y <= r) {
        br++;
        lift[br][0] = x;
        tree[x].push_back(br);
        int w = br;
        dekart(y,r,c,br);
        st[x]+=st[w];
    }
}

void dude(long long x) {
    long long sb = 0;
    for(long long v: tree[x]) {
        dude(v);
        sb+=dp[v];
    }
    dp[x] = sb;
    for(pair<long long,long long> v: star[x]) {
        long long p = pos[v.first];
        dp[x] = max(dp[x],sb+v.second-orange(p));
    }
    long long z = dp[x]-sb;
    upd(x,z);
    upd(x+st[x],-z);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(long long i = 1; i <= n; i++) {
        cin >> h[i];
    }
    build(1,n,1);
    dekart(1,n,LLONG_MAX,1);
    lift[1][0] = -1;
    for(long long i = 1; i < 18; i++) {
        for(long long j = 1; j <= br; j++) {
            if(lift[j][i-1] == -1) {
                lift[j][i] = -1;
            }
            else {
                lift[j][i] = lift[lift[j][i-1]][i-1];
            }
        }
    }
    long long m,sb = 0;
    cin >> m;
    for(long long i = 0; i < m; i++) {
        long long a,b,c;
        cin >> a >> b >> c;
        sb+=c;
        long long y = pos[a];
        for(long long j = 17; j >= 0; j--) {
            if(lift[y][j] != -1 && banana[lift[y][j]] < b) {
                y = lift[y][j];
            }
        }
        if(banana[y] < b) {
            y = lift[y][0];
        }
        star[y].push_back({a,c});
    }
    dude(1);
    cout << sb-dp[1];
    return 0;
}