Submission #881825

#	Time	Username	Problem	Language	Result	Execution time	Memory
881825		Zero_OP	Building Bridges (CEOI17_building)	C++14	0 / 100	53 ms	19796 KiB

building

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

typedef long long ll;
typedef long double ld;

struct LiChao{
    struct line{
        ll a, b;
        ll eval(ll x){ return a*x+b; }
    };

    line st[N<<2];

    void update(int id, int l, int r, line d){
        if(l==r){
            if(st[id].eval(l)>d.eval(l)) st[id]=d;
        }
        else{
            int m=l+r>>1;
            if(st[id].a<d.a) swap(st[id], d);
            if(st[id].eval(m)>d.eval(m)){
                swap(st[id], d);
                update(id<<1, l, m, d);
            }
            else{
                update(id<<1|1, m+1, r, d);
            }
        }
    }

    void insertLine(int lim, line d){
        update(1, 1, lim, d);
    }

    ll query(int id, int l, int r, int x){
        if(l==r) return st[id].eval(x);
        int m=l+r>>1;
        if(x<=m) return min(st[id].eval(x), query(id<<1, l, m, x));
        else return min(st[id].eval(x), query(id<<1|1, m+1, r, x));
    }

    ll getMin(int lim, int x){
        return query(1, 1, lim, x);
    }
} lichaoTree;

int n, h[N];
ll dp[N], w[N];

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

//    #define task "XAYCAU"
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], w[i] += w[i - 1];

    lichaoTree.insertLine(1000000, {- 2 * h[1], h[1] * h[1] + dp[1] - w[1]});
    for(int i = 2; i <= n; ++i){
        dp[i] = w[i - 1] + h[i] * h[i] + lichaoTree.getMin(1000000, h[i]);
        lichaoTree.insertLine(1000000, {-2 * h[i], h[i] * h[i] + dp[i] - w[i]});
    }

    for(int i = 1; i <= n; ++i) cout << dp[i] << " \n"[i == n];

    cout << dp[n];
    return 0;
}

Compilation message (stderr)

building.cpp: In member function 'void LiChao::update(int, int, int, LiChao::line)':
building.cpp:23:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |             int m=l+r>>1;
      |                   ~^~
building.cpp: In member function 'll LiChao::query(int, int, int, int)':
building.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int m=l+r>>1;
      |               ~^~

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