Submission #313357

#	Time	Username	Problem	Language	Result	Execution time	Memory
313357		mohamedsobhi777	Building Bridges (CEOI17_building)	C++14	100 / 100	58 ms	9080 KiB

building

#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 2e5 + 7 , mod = 1e9 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n ; 
ll ans[N]; 
ll h[N], w[N] ; 
ll pref[N] ; 
vector<pair<ll,ll> > cht ; 

#define MAXLC 1000000000
#define INF (1LL<<60)

inline ll f(ll m, ll b, int x) {
        return m * x + b;
}
ll eval(int l, int r){
        ll diff = h[r] - h[l] ; 
        return 1ll * diff * diff + pref[r - 1] - pref[l] ; 
}

struct lc_node {
        ll m = 0, b = INF;
        lc_node *l = nullptr, *r = nullptr;

        ~lc_node() { delete l; delete r; }

        void add_line(ll nm, ll nb, int lo=0, int hi=MAXLC) {
                int mid = (lo + hi) / 2;
                bool bl = f(nm, nb, lo) < f(m, b, lo);
                bool bm = f(nm, nb, mid) < f(m, b, mid);
                bool bh = f(nm, nb, hi) < f(m, b, hi);
                if (bm) {
                        swap(nm, m);
                        swap(nb, b);
                }
                if (lo == hi || nb == INF)
                        return;
                else if (bl != bm) {
                        if (!l) l = new lc_node;
                        l->add_line(nm, nb, lo, mid - 1);
                }
                else if (bh != bm) {
                        if (!r) r = new lc_node;
                        r->add_line(nm, nb, mid + 1, hi);
                }
        }

        ll get(int x, int lo=0, int hi=MAXLC) {
                int mid = (lo + hi) / 2;
                ll ret = f(m, b, x);
                if (l && x < mid)
                        ret = min(ret, l->get(x, lo, mid - 1));
                if (r && x > mid)
                        ret = min(ret, r->get(x, mid + 1, hi));
                return ret;
        }

        void clear() {
                delete l; delete r;
                m = 0, b = INF, l = nullptr, r = nullptr;
        }

} lc;

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n;  

        for(int i = 1 ;i <= n ; ++ i){
                cin >> h[i] ; 
        }
        for(int i = 1 ; i <= n ; ++ i){
                cin >> w[i] ; 
                pref[i] += w[i] ; 
                pref[i+1]+=pref[i] ; 
        }

        for(int i = 2 ; i <= n; ++ i){
                ll ret = eval(1 , i) ;
                ll cost = 1ll * h[i] * h[i] + pref[i - 1] ; 
                ret = min(ret , lc.get(h[i]) + cost ) ; 
                ans[i] = ret ; 
                lc.add_line( -2ll * h[i] , 1ll * h[i] * h[i] - pref[i] + ans[i] ) ; 
        }
        cout<<ans[n] ; 
        return 0 ; 
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

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