oj.uz

Submission #537906

# Submission time Handle Problem Language Result Execution time Memory
537906 2022-03-15T20:24:02 Z Lobo Building Bridges (CEOI17_building) C++17
100 / 100
 204 ms 20724 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], 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 5380 KB Output is correct
2 Correct 171 ms 5412 KB Output is correct
3 Correct 186 ms 5472 KB Output is correct
4 Correct 165 ms 5236 KB Output is correct
5 Correct 132 ms 8212 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 189 ms 5380 KB Output is correct
7 Correct 171 ms 5412 KB Output is correct
8 Correct 186 ms 5472 KB Output is correct
9 Correct 165 ms 5236 KB Output is correct
10 Correct 132 ms 8212 KB Output is correct
11 Correct 151 ms 5456 KB Output is correct
12 Correct 204 ms 5332 KB Output is correct
13 Correct 97 ms 5324 KB Output is correct
14 Correct 171 ms 5480 KB Output is correct
15 Correct 170 ms 20724 KB Output is correct
16 Correct 156 ms 8204 KB Output is correct
17 Correct 44 ms 5308 KB Output is correct
18 Correct 17 ms 5312 KB Output is correct