Submission #712212

#	Time	Username	Problem	Language	Result	Execution time	Memory
712212		Jarif_Rahman	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	818 ms	62080 KiB

constellation3

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, ll x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    void add(int l, int r, ll x){
        add(l, x);
        if(r != n-1) add(r+1, -x);
    }
    ll get(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
};

void preprocess(vector<int>& h, vector<tuple<int, int, ll>>& stars, vector<vector<int>>& tree,
    vector<vector<pair<int, ll>>>& paths){
    int n = h.size(), m = stars.size();
    vector<int> o(n);
    for(int i = 0; i < n; i++) o[i] = i;

    sort(o.begin(), o.end(), [&](int a, int b){
        return h[a] > h[b];
    });
    sort(stars.begin(), stars.end(), [](tuple<int, int, ll> a, tuple<int, int, ll> b){
        return get<1>(a) < get<1>(b);
    });

    tree.resize(n+1);
    paths.resize(n+1);
    set<tuple<int, int, int>> ranges;
    set<pair<int, ll>> points;
    ranges.insert({0, 0, n-1});

    for(int _i = 0, i = o[_i]; _i < n; _i++, i = o[_i]){
        while(!stars.empty() && get<1>(stars.back()) > h[i]){
            auto [x, y, c] = stars.back();
            stars.pop_back();
            points.insert({x, c});
        }
        auto it = prev(ranges.upper_bound(make_tuple(i, 1000000000, 1000000000)));
        auto [l, p, r] = *it;
        ranges.erase(it);
        
        tree[p].pb(i+1);

        while(1){
            auto it = points.lower_bound(make_pair(l, -1LL));
            if(it == points.end() || it->f > r) break;
            paths[p].pb({it->f+1, it->sc});
            points.erase(it);
        }

        if(l < i){
            int nd = tree.size();
            tree.pb({}), paths.pb({});
            tree[p].pb(nd);
            ranges.insert({l, nd, i-1});
        }
        if(i < r){
            int nd = tree.size();
            tree.pb({}), paths.pb({});
            tree[p].pb(nd);
            ranges.insert({i+1, nd, r});
        }
    }
}

int N, M, n;
vector<vector<int>> tree;
vector<vector<pair<int, ll>>> paths;
vector<int> pos, sz;
vector<ll> dp;
BIT bit(0);
ll sum = 0;

int intime = 0;
void pre_dfs(int nd){
    pos[nd] = intime++;
    for(int x: tree[nd]) pre_dfs(x), sz[nd]+=sz[x];
}

void dfs(int nd){
    ll sm = 0;
    for(int x: tree[nd]) dfs(x), sm+=dp[x], dp[nd]+=dp[x];
    for(int x: tree[nd]) bit.add(pos[x], pos[x]+sz[x]-1, sm-dp[x]);
    for(auto [x, c]: paths[nd]) dp[nd] = max(dp[nd], c+bit.get(pos[x]));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    vector<int> h(N);
    for(int &x: h) cin >> x;
    cin >> M;
    vector<tuple<int, int, ll>> stars(M);
    for(auto &[x, y, c]: stars) cin >> x >> y >> c, x--, sum+=c;

    preprocess(h, stars, tree, paths);

    n = tree.size();
    pos.resize(n);
    sz.assign(n, 1);
    dp.assign(n, 0);
    bit = BIT(n);

    pre_dfs(0);
    dfs(0);
    cout << sum-dp[0] << "\n";
}

Compilation message (stderr)

constellation3.cpp: In function 'void preprocess(std::vector<int>&, std::vector<std::tuple<int, int, long long int> >&, std::vector<std::vector<int> >&, std::vector<std::vector<std::pair<int, long long int> > >&)':
constellation3.cpp:34:23: warning: unused variable 'm' [-Wunused-variable]
   34 |     int n = h.size(), m = stars.size();
      |                       ^

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