oj.uz

Submission #507568

# Submission time Handle Problem Language Result Execution time Memory
507568 2022-01-12T18:23:22 Z Lobo Building Bridges (CEOI17_building) C++17
0 / 100
 27 ms 5316 KB 
#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)
            lb = 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)
            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));
    }
    else {
        bg[idb] = ed[idb] = -1;
    }

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

    //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];
        // cout << i << " = " << id1 << "   " << ans1 << endl;

        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] - w[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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5276 KB Output is correct
2 Incorrect 26 ms 5316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -