Submission #507590

#	Time	Username	Problem	Language	Result	Execution time	Memory
507590		Lobo	Building Bridges (CEOI17_building)	C++17	100 / 100	500 ms	12888 KiB

building

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000
#define hmax 1000000
int n, h[maxn], w[maxn], ps[maxn];
int bg[maxn], ed[maxn], a[maxn], b[maxn];
set<pair<int,int>> hull;

int f(int id, int x) {
    return a[id]*x + b[id];
}

void ins(int id) {
    //f(id) = a[id]*x + b[id];

    //onde comeca o id
    int lb = 0;
    int rb = hmax;
    int ansb = -1;
    while(lb <= rb) {
        int mid = (lb+rb)/2;
        //quer saber se f(id) e o melhor no ponto mid
        auto it1 = hull.lower_bound(mp(mid,-inf));
        int id1 = it1->sc;

        if(f(id,mid) <= f(id1,mid)) {
            //id e otimo em mid, o comeco esta em (lb,mid)
            ansb = mid;
            rb = mid-1;
        }
        else {
            //id nao e otimo em mid, comeco esta em (mid+1,rb)
            if(a[id] < a[id1]) {
                //comeco esta em (mid+1,rb)
                lb = mid+1;
            }
            else {
                rb = mid-1;
            }
        }
    }

    //nao e bom em nenhum ponto
    if(ansb == -1) return;

    //onde comeca o id
    int le = 0;
    int re = hmax;
    int anse = -1;
    while(le <= re) {
        int mid = (le+re)/2;
        //quer saber se f(id) e o melhor no ponto mid
        auto it1 = hull.lower_bound(mp(mid,-inf));
        int id1 = it1->sc;

        if(f(id,mid) <= f(id1,mid)) {
            //id e otimo em mid, o final esta em (mid,rb)
            anse = mid;
            le = mid+1;

        }
        else {
            //id e otimo em mid, o final esta em (lb,mid-1)
            if(a[id] < a[id1]) {
                //final esta em (mid+1,rb)
                le = mid+1;
            }
            else {
                re = mid-1;
            }
        }
    }

    //id e otimo em (ansb, anse)

    auto itb = hull.lower_bound(mp(ansb,-inf));
    int idb = itb->sc;
    auto ite = hull.lower_bound(mp(anse,-inf));
    int ide = ite->sc;

    ite++;
    hull.erase(itb,ite);
    
    //se for interir idb
    if(bg[idb] < ansb) {
        ed[idb] = ansb-1;
        hull.insert(mp(ed[idb],idb));
    }

    //se for interir ide
    if(ed[ide] > anse) {
        bg[ide] = anse+1;
        hull.insert(mp(ed[ide],ide));
    }
    

    //insere id
    bg[id] = ansb;
    ed[id] = anse;
    hull.insert(mp(ed[id],id));


}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        ps[i] = ps[i-1] + w[i];
    }

    bg[0] = 0;
    ed[0] = hmax;
    a[0] = 0;
    b[0] = inf;
    hull.insert(mp(hmax,0));


    a[n] = -2*h[n];
    b[n] = h[n]*h[n] + ps[n-1];
    ins(n);

    for(int i = n-1; i >= 2; i--) {
        auto it1 = hull.lower_bound(mp(h[i],-inf));
        int id1 = it1->sc;
        int ans1 = f(id1,h[i]) + h[i]*h[i] - ps[i];

        a[i] = -2*h[i];
        b[i] = ans1 + h[i]*h[i] + ps[i-1];
        ins(i);
    }


    auto it = hull.lower_bound(mp(h[1],-inf));
    int id = it->sc;
    int ans = f(id,h[1]) + h[1]*h[1] - ps[1];

    cout << ans << endl;

}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40