Submission #1291822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291822		Math4Life2020	Meetings (IOI18_meetings)	C++20	4 / 100	5593 ms	2508 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>; using ti = array<ll,3>;
const ll INF = 1e18;


vector<ll> gseg(vector<ll> H) { //get segment values
    ll N = H.size();
    ll xl = 0; ll xr = N-1;
    if (H.size()==0) {
        return vector<ll>(0);
    }
    set<pii> hpmax; //h pair max
    for (ll i=0;i<N;i++) {
        hpmax.insert((pii){H[i],i});
    }
    ll T = 0; //# of iteration
    vector<ll> v1,v2; //val1/val2 vectors
    while (xl<=xr) {
        assert(!hpmax.empty());
        auto A0 = *(--hpmax.end()); hpmax.erase(--hpmax.end());
        ll hmax = A0.first; ll x = A0.second;
        assert(x>=0 && x<N);
        if (x<xl || xr<x) {
            continue; //break loop & restart
        }
        T++;
        ll a = (x-xl); ll b = (xr-x);
        if (a<b) {
            //recursion call on left
            vector<ll> rcall;
            for (ll x0=xl;x0<x;x0++) {
                rcall.push_back(H[x0]);
            }
            vector<ll> qryL = gseg(rcall);
            if (qryL.size()==0) {
                qryL.push_back(0);
            }
            ll val1 = qryL[0]+hmax*(xr-x+1);
            ll val2 = (x-xl+1)*hmax;
            v1.push_back(val1);
            v2.push_back(val2);
            xl = x+1;
        } else {
            //instead call on right
            vector<ll> rcall;
            for (ll x0=(x+1);x0<=xr;x0++) {
                rcall.push_back(H[x0]);
            }
            vector<ll> qryL = gseg(rcall);
            if (qryL.size()==0) {
                qryL.push_back(0);
            }
            ll val1 = qryL[0]+hmax*(x-xl+1);
            ll val2 = (xr-x+1)*hmax;
            v1.push_back(val1);
            v2.push_back(val2);
            xr = x-1;
        }
    }
    assert(T==v1.size());
    assert(T==v2.size());
    vector<ll> ansv;
    ansv.push_back(0);
    //cout << "T="<<T<<"\n";
    for (ll t=(T-1);t>=0;t--) {
        //cout << "reverse v1,v2="<<v1[t]<<","<<v2[t]<<"\n";
        ansv.push_back(min(v1[t],v2[t]+ansv.back()));
    }
    vector<ll> iansv;
    for (ll t=0;t<=T;t++) {
        iansv.push_back(ansv[T-t]);
    }
    return iansv;
}

ll ansqry(vector<ll> H) {
    return gseg(H)[0];
}

ll ansqry2(vector<ll> H) {
    ll N = H.size();
    ll ans = INF;
    for (ll x=0;x<N;x++) {
        ll cnd = H[x];
        ll rmax = H[x];
        for (ll y=(x+1);y<N;y++) {
            rmax = max(rmax,H[y]);
            cnd += rmax;
        }
        rmax = H[x];
        for (ll y=(x-1);y>=0;y--) {
            rmax = max(rmax,H[y]);
            cnd += rmax;
        }
        ans = min(ans,cnd);
    }
    return ans;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    ll N = H.size();
    ll Q = L.size();
    vector<ll> ans(Q);
    for (ll q=0;q<Q;q++) {
        vector<ll> Hqry;
        for (ll x=L[q];x<=R[q];x++) {
            Hqry.push_back(H[x]);
        }
        ans[q]=ansqry(Hqry);
    }
    return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40