제출 #537906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537906		Lobo	Building Bridges (CEOI17_building)	C++17	100 / 100	204 ms	20724 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], av[maxn], bv[maxn];
set<pair<pair<int,int>,pair<int,int>>, greater<pair<pair<int,int>,pair<int,int>>>> cht;
set<pair<pair<int,int>,pair<int,int>>> chtlr;
//cht -> a,b,l,r
//chtlr -> l,r,a,b

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

dbl interx(int a1, int b1, int a2, int b2) {
    return (dbl) (b2-b1)/(a1-a2);
}

void resetcht() {
    cht.clear();
    chtlr.clear();

    cht.insert(mp(mp(0,inf),mp(-inf1,+inf1)));
    chtlr.insert(mp(mp(-inf1,+inf1),mp(0,inf)));
}

void attcht(int a, int b) {
    //f(x) = a*x + b
    //pega qual o lugar que eu seria colocado no set
    auto it = cht.upper_bound(mp(mp(a,b),mp(0,0)));

    //left = (beg,it-1)
    //right = (it,end-1)
    vector<pair<pair<int,int>,pair<int,int>>> rem, add;

    int ansr = -inf1;
    int ansl = +inf1;
    //primeiro tiro tudo da esquerda
    auto itl = it;
    //al >= a
    while(itl != cht.begin()) {
        itl--; //ve se consegue tirar it1

        int al = itl->fr.fr;
        int bl = itl->fr.sc;
        int l = itl->sc.fr;
        int r = itl->sc.sc;

        //se em l o novo for melhor que o antigo, entao apaga o antigo
        if(f(a,b,l) <= f(al,bl,l)) {
            ansl = l;
            ansr = max(ansr,r);
            rem.pb(mp(mp(al,bl),mp(l,r)));
        }
        else if(f(a,b,r) <= f(al,bl,r)) {
            //find the intersect (a,b) and (al,bl)
            //a != al
            //f(a,b) >= f(al,bl) in ceil(x)
            int x = ceil(interx(a,b,al,bl));
            rem.pb(mp(mp(al,bl),mp(l,r)));
            add.pb(mp(mp(al,bl),mp(l,x-1)));
            ansr = max(ansr,r);
            ansl = x;
            break;
        }
        else {
            break;
        }
    }

    auto itr = it;
    //al <= a
    while(itr != cht.end()) {
        //ve se consegue tirar itr

        int ar = itr->fr.fr;
        int br = itr->fr.sc;
        int l = itr->sc.fr;
        int r = itr->sc.sc;

        //se em r o novo for melhor que o antigo, entao apaga o antigo
        if(f(a,b,r) <= f(ar,br,r)) {
            ansr = r;
            ansl = min(ansl,l);
            rem.pb(mp(mp(ar,br),mp(l,r)));
        }
        else if(f(a,b,l) <= f(ar,br,l)) {
            //find the intersect (a,b) and (ar,br)
            //a != ar
            //f(a,b) >= f(ar,br) at floor(x)
            int x = floor(interx(a,b,ar,br));
            rem.pb(mp(mp(ar,br),mp(l,r)));
            add.pb(mp(mp(ar,br),mp(x+1,r)));
            ansr = x;
            ansl = min(ansl,l);
            break;
        }
        else {
            break;
        }
        itr++;
    }

    for(auto x : rem) {
        cht.erase(x);
        chtlr.erase(mp(x.sc,x.fr));
    }

    for(auto x : add) {
        cht.insert(x);
        chtlr.insert(mp(x.sc,x.fr));
    }

    if(ansl <= ansr) {
        cht.insert(mp(mp(a,b),mp(ansl,ansr)));
        chtlr.insert(mp(mp(ansl,ansr),mp(a,b)));
    }
}

int qrr(int x) {
    auto it = chtlr.upper_bound(mp(mp(x,inf),mp(0,0)));
    it--;
    int a = it->sc.fr;
    int b = it->sc.sc;

    return f(a,b,x);
}

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];
    }

    resetcht();
    
    av[n] = -2*h[n];
    bv[n] = h[n]*h[n] + ps[n-1];
    attcht(av[n],bv[n]);

    for(int i = n-1; i >= 2; i--) {
        int ans1 = qrr(h[i]) + h[i]*h[i] - ps[i];
        av[i] = -2*h[i];
        bv[i] = ans1 + h[i]*h[i] + ps[i-1];
        attcht(av[i],bv[i]);
    }

    int ans = qrr(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