Submission #513223

#	Time	Username	Problem	Language	Result	Execution time	Memory
513223		wiwiho	Constellation 3 (JOI20_constellation3)	C++14	35 / 100	491 ms	524292 KiB

constellation3

#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;

struct seg{
    int l, r, id;
    bool operator<(seg b) const {
        return l < b.l;
    }
};

ostream& operator<<(ostream& o, seg s){
    return o << '(' << s.l << ',' << s.r << ',' << s.id << ')';
}

vector<vector<int>> g, star;
vector<int> lp, rp;
vector<int> a, X, Y;
vector<ll> C;

vector<vector<ll>> dp;
vector<ll> sub;
int n;

void dfs(int now){
    ll total = 0;
    for(int i : star[now]) total += C[i];
    sub[now] = total;

    ll sum = 0;
    
    for(int i : g[now]){
        dfs(i);
    }

    vector<ll> tmp(n + 1);
    for(int i = 0; i <= n; i++){
        for(int j : g[now]) tmp[i] += dp[j][i];
    }

    ll cn = total + tmp[0];
    for(int i : star[now]){
        int x = X[i];
        cn = min(cn, tmp[x] + total - C[i]);
    }
    for(int i = 0; i <= n; i++){
        if(lp[now] <= i && i <= rp[now]) dp[now][i] = total + tmp[i];
        else dp[now][i] = cn;
    }
}

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

    cin >> n;

    vector<pii> e;

    a.resize(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        e.eb(mp(a[i], i));
    }

    int m;
    cin >> m;
    X.resize(m + 1);
    Y.resize(m + 1);
    C.resize(m + 1);
    for(int i = 1; i <= m; i++){
        cin >> X[i] >> Y[i] >> C[i];
        e.eb(mp(Y[i], -i));
    }

    gsort(e);

    set<seg> st;
    st.insert(seg({1, n, 1}));
    int ts = 1;
    g.resize(2);
    star.resize(2);
    lp.resize(2);
    rp.resize(2);
    lp[1] = 1;
    rp[1] = n;

    for(int i = 0; i < e.size(); ){
        
        int y = e[i].F;

        for(; i < e.size() && e[i].F == y; i++){

            if(e[i].S > 0){
                int pos = e[i].S;
                
                auto it = st.upper_bound(seg({pos, 0, 0}));
                if(it == st.begin()) continue;
                it--;
                if(it->r < pos) continue;

                int l = it->l, r = it->r;
                int id = it->id;
                st.erase(it);
                if(l < pos){
                    st.insert(seg({l, pos - 1, ++ts}));
                    g.eb(); star.eb(); lp.eb(); rp.eb();
                    g[id].eb(ts);
                    lp[ts] = l;
                    rp[ts] = pos - 1;
                }
                if(pos < r){
                    st.insert(seg({pos + 1, r, ++ts}));
                    g.eb(); star.eb(); lp.eb(); rp.eb();
                    g[id].eb(ts);
                    lp[ts] = pos + 1;
                    rp[ts] = r;
                }
                //cerr << "split\n";
                //printv(st, cerr);
                continue;
            }

            int id = -e[i].S;
            //cerr << "add star " << id << "\n";
            //printv(st, cerr);
            int x = X[id];
            auto it = st.upper_bound(seg({x, 0, 0}));
            it--;

            int v = it->id;
            star[v].eb(id);
        }

    }

    /*for(int i = 1; i <= ts; i++){
        cerr << "seg " << i << " " << lp[i] << "  ";
        printv(star[i], cerr);
        printv(g[i], cerr);
    }*/

    dp.resize(ts + 1, vector<ll>(n + 1));
    sub.resize(ts + 1);
    dfs(1);

    cout << dp[1][0] << "\n";
    
    return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'void dfs(int)':
constellation3.cpp:46:8: warning: unused variable 'sum' [-Wunused-variable]
   46 |     ll sum = 0;
      |        ^~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i = 0; i < e.size(); ){
      |                    ~~^~~~~~~~~~
constellation3.cpp:108:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(; i < e.size() && e[i].F == y; i++){
      |               ~~^~~~~~~~~~

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