Submission #673962

#	Time	Username	Problem	Language	Result	Execution time	Memory
673962		jeroenodb	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	200 ms	61984 KiB

constellation3

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct el {
    int y,c;
    ll mydp;
    bool operator<(const el& o ) const {
        return y>o.y;
    }
};
struct DS {
    ll lazy=0, mn = 0;

    // mn is min dp value inside this DS.
    // sum is the sum of the currently "bad" stars.
    priority_queue<el> pq;
    void addStart(int y, int c, ll mydp=0) {
        lazy+=c;
        pq.push({y,c,mydp+mn-lazy});
        mn+=c;
    }
    void add(int y, int c, ll mydp=0) {
        pq.push({y,c,mydp-lazy});
    }
    void clean(int h) {
        // everything below h is safe.
        while(!pq.empty() and pq.top().y<=h) {
            mn = min(mn,lazy+pq.top().mydp);
            pq.pop();
        }
    }
    int size() {
        return pq.size();
    }

};
void merge(DS& a, DS& b) {
    if(a.size()<b.size()) swap(a,b);
    a.lazy+=b.mn;
    auto oldmn = a.mn;
    a.mn+=b.mn;
    
    while(b.size()) {
        auto e = b.pq.top();
        e.mydp+=b.lazy+oldmn;
        a.add(e.y,e.c,e.mydp);
        b.pq.pop();
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vi a(n);
    for(auto& i : a) cin >> i;
    #ifdef DEBUG
    vector<vi> adj(n);
    #else
    vector<basic_string<int>> adj(n);
    #endif
    int root=-1;
    {
    vi l(n);
    for(int i=0;i<n;++i) {
        l[i] = i-1;
        while(l[i]>=0 and a[l[i]]<a[i]) {
            l[i] = l[l[i]];
        }
    }
    vi r(n);
    for(int i=n-1;i>=0;--i) {
        r[i] = i+1;
        while(r[i]<n and a[r[i]]<=a[i]) {
            r[i]=r[r[i]];
        }
    }
    
    for(int i=0;i<n;++i) {
        if(l[i]<0 and r[i]>=n) root=i;
        else if(r[i]<n and (l[i]<0 or a[l[i]]>a[r[i]])) adj[r[i]].push_back(i);
        else adj[l[i]].push_back(i);
    }
    }
    vector<vector<pi>> stars(n);
    int m; cin >> m;
    while(m--) {
        int x,y,c; cin >> x >> y >> c;
        --x;
        stars[x].push_back({y,c});
    }
    vector<DS> ds(n);
    auto dfs = [&](auto&& self, int at) -> void {
        for(auto [y,c] : stars[at]) {
            ds[at].addStart(y,c);
        }
        for(int to : adj[at]) {
            self(self,to);
            ds[to].clean(a[at]);
            merge(ds[at],ds[to]);
        }
    };
    dfs(dfs,root);
    auto& dsr = ds[root];
    dsr.clean(1e9);
    ll ans=dsr.mn;
    cout << ans << '\n';
}

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