Submission #1161778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161778		Math4Life2020	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	252 ms	52120 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 2e5+5; const ll INF = 1e18;

struct Node {
    ll cht = 0;
    ll lzadd = 0; //lazy add tag
    ll vnh = 0; //value at no height
    map<ll,ll> mht; //map: height -> value, must be strictly increasing
    Node(){}
    void print() {
        return;
        cout << "cht="<<cht<<", lzadd="<<lzadd<<", vnh="<<vnh<<"\n";
        cout << "mht: \n";
        for (pii p0: mht) {
            cout << "term: "<<p0.first<<" "<<p0.second<<"\n";
        }
    }
    Node(ll _cht, vector<pii> velem) {
        cht = _cht;
        sort(velem.begin(),velem.end());
        ll cmax = 0;
        for (pii p0: velem) {
            if (p0.second>cmax) {
                mht[p0.first]=p0.second;
                cmax = p0.second;
            }
        }
    }
    void hfix(ll hf) { //fix height
        if (hf<cht) {
            return;
        }
        //cout << "\nfixing height\n";
        cht = hf;
        while (!mht.empty()) {
            auto A0 = mht.begin();
            pii p0 = *A0;
            if (p0.first<=hf) {
                vnh = max(vnh,p0.second);
                mht.erase(A0);
            } else {
                break;
            }
        }
        print();
    }
    bool anl(ll x) { //1 if made change
        assert(!mht.empty());
        auto A0 = mht.find(x);
        if (A0==mht.end()) {
            return 0;
        }
        if (A0 == mht.begin()) {
            ll vf = (*A0).second;
            if (vf<=vnh) {
                mht.erase(A0);
                return 1;
            }
        } else {
            auto Ap = prev(A0);
            if ((*Ap).second>=(*A0).second) {
                mht.erase(A0);
                return 1;
            }
        }
        auto A1 = next(A0);
        if (A1!=mht.end()) {
            if ((*A1).second<=(*A0).second) {
                mht.erase(A1);
                anl(x);
                return 1;
            }
        }
        return 0;
    }

    void merge(Node n1) {
        //assume both height annealed
        //vnh = max(vnh,n1.vnh);
        //while (!mht.empty() && anl((*mht.begin()).first));
        for (pii p0: n1.mht) {
            if (mht.find(p0.first)==mht.end()) {
                mht[p0.first]=-INF;
            }
            mht[p0.first]=max(p0.second-n1.vnh+vnh,mht[p0.first]);
            anl(p0.first);
        }
        lzadd += (n1.lzadd+n1.vnh);
    }
    ll gmax() {
        if (mht.size()!=0) {
            auto A0 = --mht.end();
            //cout << (*A0).second<<" = return val \n";
            return ((*A0).second+lzadd);
        }
        return (vnh+lzadd);
    }
};

ll dsuf[Nm];
Node* dp[Nm];

ll getf(ll x) {
    if (dsuf[x]==x) {
        return x;
    }
    return (dsuf[x]=getf(dsuf[x]));
}

void fz(ll a, ll b) {
    a = getf(a);
    b = getf(b);
    if (a==b) {
        return;
    }
    if (dp[a]->mht.size()>dp[b]->mht.size()) {
        swap(a,b);
    } //thus merge a into b
    dsuf[a]=b;
    //cout << "-----before merge:---\n";
    dp[a]->print();
    //cout << "----and----\n";
    dp[b]->print();
    ll cht = max(dp[b]->cht,dp[a]->cht);
    dp[a]->hfix(cht);
    dp[b]->hfix(cht);
    dp[b]->merge(*dp[a]);
    //cout << "-----after:-----\n";
    dp[b]->print();
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    for (ll i=0;i<N;i++) {
        dsuf[i]=i;
    }
    ll A[N];
    vector<pii> vas;
    for (ll i=0;i<N;i++) {
        cin >> A[i];
        vas.push_back({A[i],i}); 
    }
    sort(vas.begin(),vas.end());
    ll M; cin >> M;
    vector<pii> velem[N];
    ll sumc = 0;
    for (ll i=0;i<M;i++) {
        ll x,y,c; cin >> x >> y >> c;
        sumc+=c;
        x--;
        velem[x].push_back({y,c});
    }
    //cout << "sumc="<<sumc<<"\n";
    for (ll i=0;i<N;i++) {
        dp[i] = new Node(A[i],velem[i]);
    }
    for (pii p0: vas) {
        ll ic = p0.second;
        if (ic>0 && A[ic-1]<=A[ic]) {
            //cout << "\nfusing "<<(ic)<<","<<(ic-1)<<"\n";
            fz(ic,ic-1);
        }
        if (ic<(N-1) && A[ic+1]<=A[ic]) {
            //cout << "\nfusing "<<(ic)<<","<<(ic+1)<<"\n";
            fz(ic,ic+1);
        }
    }
    cout << (sumc-dp[getf(0)]->gmax()) <<"\n";
}

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