Submission #1170769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170769		SmuggingSpun	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	313 ms	82472 KiB

constellation3

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
const int lim = 2e5 + 5;
int n, m, time_dfs = 0, log_v[lim], low[lim], tail[lim], up[lim][18];
pair<int, int>spt_a[lim][18];
int get_max_index(int l, int r){
    int k = log_v[r - l + 1];
    return max(spt_a[l][k], spt_a[r - (1 << k) + 1][k]).second;
}
vector<int>g[lim];
vector<pair<int, int>>path[lim];
ll bit[lim], dp[lim];
void update(int p, ll x){
    for(; p <= n; p += p & -p){
        bit[p] += x;
    }
}
void update(int l, int r, ll x){
    update(l, x);
    update(r + 1, -x);
}
ll get(int p){
    ll ans = 0;
    for(; p > 0; p -= p & -p){
        ans += bit[p];
    }
    return ans;
}
int build(int l, int r){
    if(l > r){
        return -1;
    }
    int p = get_max_index(l, r), left = build(l, p - 1), right = build(p + 1, r);
    if(left != -1){
        g[p].emplace_back(left);
    }
    if(right != -1){
        g[p].emplace_back(right);
    }
    return p;
}
void dfs_1(int s){
    low[s] = ++time_dfs;
    for(int& d : g[s]){
        up[d][0] = s;
        for(int i = 1; i < 18; i++){
            up[d][i] = up[up[d][i - 1]][i - 1];
        }
        dfs_1(d);
    }
    tail[s] = time_dfs;
}
void dfs_2(int s){
    for(int& d : g[s]){
        dfs_2(d);
        dp[s] += dp[d];    
    }
    if(g[s].size() == 2){
        update(low[g[s][0]], tail[g[s][0]], dp[g[s][1]]);
        update(low[g[s][1]], tail[g[s][1]], dp[g[s][0]]);
    }
    for(auto& [d, c] : path[s]){
        ll cost = get(low[d]) + c;
        for(int& v : g[d]){
            cost += dp[v];
        }
        maximize(dp[s], cost);
    }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    log_v[0] = -1;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> spt_a[i][0].first;
        log_v[spt_a[i][0].second = i] = log_v[i >> 1] + 1;
    }
    for(int j = 1; j < 18; j++){
        for(int i = 1; i + (1 << j) - 1 <= n; i++){
            spt_a[i][j] = max(spt_a[i][j - 1], spt_a[i + (1 << (j - 1))][j - 1]);
        }
    }
    int root = build(1, n);
    memset(up, 0, sizeof(up));
    dfs_1(root);
    cin >> m;
    ll sum_c = 0;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        sum_c += c;
        int vertex = x;
        for(int j = 17; j > -1; j--){
            int candidate = up[vertex][j];
            if(candidate != 0 && spt_a[candidate][0].first < y){
                vertex = candidate;
            }
        }
        path[vertex].emplace_back(x, c);
    }
    memset(dp, 0, sizeof(dp));
    memset(bit, 0, sizeof(bit));
    dfs_2(root);
    cout << sum_c - dp[root];
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:80:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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