Submission #507739

#	Time	Username	Problem	Language	Result	Execution time	Memory
507739		couplefire	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	460 ms	106584 KiB

constellation3

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

const int N = 200005;

int n, m, arr[N], st[N][20], lg[N];
vector<int> pos[N];
int vv[N], dep[N], top, up[N][20], rt;
ll dp[N], bit[N], sum[N];
int tin[N], tout[N], tid;
vector<int> adj[N];
vector<pair<int, int>> stuff[N];

void update(int i, ll x) {
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}
 
ll query(int i) {
    ll ret = 0;
    while (i) {
        ret += bit[i];
        i -= i & -i;
    }
    return ret;
}

int build(int l, int r){
    if(r<l) return -1;
    int tmp = lg[r-l+1];
    int mx = max(st[l][tmp], st[r-(1<<tmp)+1][tmp]);
    vector<int> cur_pos = {l-1};
    for(auto i = lower_bound(pos[mx].begin(), pos[mx].end(), l)-pos[mx].begin(); i<(int)pos[mx].size() && pos[mx][i]<=r; ++i)
        cur_pos.push_back(pos[mx][i]);
    cur_pos.push_back(r+1);
    vector<int> cur_child;
    for(int i = 0; i<(int)cur_pos.size()-1; ++i){
        cur_child.push_back(build(cur_pos[i]+1, cur_pos[i+1]-1));
        if(cur_child.back()==-1) cur_child.pop_back();
    }
    for(auto x : cur_child)
        adj[top].push_back(x);
    for(auto x : cur_pos)
        if(x!=l-1 && x!=r+1)
            vv[x] = top;
    dep[top] = mx;
    ++top; return top-1;
}

void dfs1(int v, int p){
    up[v][0] = p;
    for(int i = 1; i<20; ++i)
        up[v][i] = up[up[v][i-1]][i-1];
    tin[v] = ++tid;
    for(auto u : adj[v])
        dfs1(u, v);
    tout[v] = tid;
}

void dfs2(int x) {
    for (int i : adj[x]) {
        dfs2(i);
        sum[x] += dp[i];
    }
    for (auto [y, c] : stuff[x]) {
        dp[x] = max(dp[x], query(tin[y]) + c);
    }
    update(tin[x], -dp[x]);
    update(tout[x] + 1, dp[x]);
    dp[x] += sum[x];
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i<=n; ++i)
        cin >> arr[i], pos[arr[i]].push_back(i);
    for(int i = 1; i<=n; ++i)
        st[i][0] = arr[i];
    for(int i = n; i>=1; --i)
        for(int j = 1; j<20; ++j)
            if(i+(1<<j)-1<=n) st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
    for(int i = 1; i<=n/2; ++i)
        lg[i<<1] = lg[i<<1|1] = lg[i]+1;
    rt = build(1, n); cin >> m; ll sum = 0;
    dfs1(rt, rt);
    while(m--){
        int x, y, c; cin >> x >> y >> c;
        sum += c;
        int tmp = vv[x];
        int cur = tmp;
        for(int j = 19; j>=0; --j)
            if(dep[up[cur][j]]<y) cur = up[cur][j];
        stuff[cur].push_back({tmp, c});
    }
    dfs2(rt);
    cout << sum-dp[rt] << '\n';
}

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