Submission #597586

#	Time	Username	Problem	Language	Result	Execution time	Memory
597586		OttoTheDino	Building Bridges (CEOI17_building)	C++17	100 / 100	103 ms	16872 KiB

building

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

//let's implement cht then :)))))))))

const ll inf = 1e9;

ll cdiv (ll a, ll b) {
    return  a / b + !(((a < 0) != (b < 0)) || !(a % b));
}

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

    ll n, s = 0;
    cin >> n;
    ll h[n+1], w[n+1], x[n+1], dp[n+1];

    set<pll,greater<pll>> stk;
    set<pll> stx;

    rep (i,1,n) cin >> h[i];
    rep (i,1,n) {
        cin >> w[i];
        s += w[i];
    }

    dp[1] = h[1]*h[1] - w[1];
    stk.insert({-2*h[1],1});  
    stx.insert({-inf,1});  
    x[1] = -inf;

    rep (i,2,n) {
        auto iti = stx.upper_bound({h[i], inf});
        --iti;

        ll u = (*iti).se;

        dp[i] = dp[u] + -2*h[u]*h[i] + h[i] * h[i] - w[i];

        if (i==n) cout << s+dp[n] << "\n";

        else {
            //add an element to the cht
            dp[i] += h[i]*h[i];

            auto it = stk.upper_bound({-2*h[i], -inf});
            
            bool beg = 0;
            if (it!=stk.begin()) {
                --it;
                while (true) {
                    if ((*it).fi==-2*h[i]) {
                        if (dp[i] >= dp[(*it).se]) break;
                    }
                    else {
                        ll nx = cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi);
                        if (nx>x[(*it).se]) break;
                    }
                    stx.erase({x[(*it).se], (*it).se});
                    it = stk.erase(it);
                    if (it==stk.begin()) {
                        beg = 1;
                        break;
                    }
                    --it;
                }
            }
            else beg = 1;

            if (beg) {
                stk.insert({-2*h[i], i});
                x[i] = -inf;
                stx.insert({-inf, i});
            }
            else {
                if ((*it).fi==-2*h[i]) continue;
                int X = cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi); 
                ++it;
                if (it==stk.end() || X <= x[(*it).se]) {
                    if (it!=stk.end() && X==x[(*it).se]) {
                       if (cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi)<=X) continue;
                    }
                    stx.insert({X, i});
                    stk.insert({-2*h[i],i});
                    x[i] = X;
                }
                else continue;
            }

            while (true) {
                if (it==stk.end()) break;

                int X = cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi); 
                ++it;

                if (it==stk.end()) {
                    --it;
                    stx.erase({x[(*it).se], (*it).se});
                    stx.insert({X, (*it).se});
                    x[(*it).se] = X;
                    break;
                }

                if (X >= x[(*it).se]) {
                    --it;
                    stx.erase({x[(*it).se], (*it).se}); 
                    it = stk.erase(it);
                }

                else {
                    --it;
                    stx.erase({x[(*it).se], (*it).se});
                    stx.insert({X, (*it).se});
                    x[(*it).se] = X;
                    break;
                }
            }
        }
    }


    return 0;
}

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