oj.uz

Submission #507590

# Submission time Handle Problem Language Result Execution time Memory
507590 2022-01-12T19:02:42 Z Lobo Building Bridges (CEOI17_building) C++17
100 / 100
 500 ms 12888 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)
            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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 328 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 5848 KB Output is correct
2 Correct 228 ms 6852 KB Output is correct
3 Correct 237 ms 7008 KB Output is correct
4 Correct 211 ms 6724 KB Output is correct
5 Correct 229 ms 7876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 246 ms 5848 KB Output is correct
7 Correct 228 ms 6852 KB Output is correct
8 Correct 237 ms 7008 KB Output is correct
9 Correct 211 ms 6724 KB Output is correct
10 Correct 229 ms 7876 KB Output is correct
11 Correct 194 ms 6964 KB Output is correct
12 Correct 250 ms 6916 KB Output is correct
13 Correct 88 ms 6820 KB Output is correct
14 Correct 246 ms 6940 KB Output is correct
15 Correct 500 ms 12888 KB Output is correct
16 Correct 247 ms 7940 KB Output is correct
17 Correct 25 ms 5240 KB Output is correct
18 Correct 24 ms 5320 KB Output is correct