Submission #1113788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113788		Zero_OP	Building Bridges (CEOI17_building)	C++14	100 / 100	171 ms	91800 KiB

building

//Just some random thing in my mind
#include <bits/stdc++.h>

using namespace std;

const long long inf = 4e18;

struct line{
    long long a, b, p;
    line(long long a = 0, long long b = 0, long long p = 0) : a(a), b(b), p(p) {}
    long long eval(long long x){ return a * x + b; }
    bool operator < (const long long& o) const { return p < o; }

    friend bool operator < (const line& d1, const line& d2){
        return make_pair(d1.a, d1.b) > make_pair(d2.a, d2.b);
    }
};

long long divi(long long a, long long b){
    return a / b - ((a % b) != 0 && (a ^ b) < 0);
}

void isect(line& d1, const line& d2){
    if(d1.a == d2.a) d1.p = (d1.b < d2.b ? inf : -inf);
    else d1.p = divi(d2.b - d1.b, d1.a - d2.a);
}

struct convex_hull_trick{
    deque<line> v;
    convex_hull_trick() : v() {}

    void add(long long a, long long b){
        line d(a, b, inf);
        if(!v.empty()) isect(v.back(), d);
        while((int)v.size() > 1 && v[(int)v.size() - 2].p >= v.back().p){
            v.pop_back();
            isect(v.back(), d);
        }

        v.push_back(d);
    }

//    long long query(long long x){
//        int id = lower_bound(v.begin(), v.end(), x) - v.begin();
//        return v[id].eval(x);
//    }

    long long query(long long x){
        while((int)v.size() > 1 && v[0].eval(x) >= v[1].eval(x)) v.pop_front();
        return v[0].eval(x);
    }
};

template<typename T>
void merge_sort(vector<T>& a, const vector<T>& b){
    vector<T> c;
    int i = 0, j = 0;
    while(i < (int)a.size() || j < (int)b.size()){
        if(i == (int)a.size()) c.emplace_back(b[j++]);
        else if(j == (int)b.size()) c.emplace_back(a[i++]);
        else if(a[i] < b[j]) c.emplace_back(a[i++]);
        else c.emplace_back(b[j++]);
    }
    swap(a, c);
}

const int MAX = 1e5 + 5;

int N, timerNodes, ln[MAX * 2], rn[MAX * 2];
long long dp[MAX], h[MAX], w[MAX];
vector<line> lines[MAX * 2];
vector<pair<int, int>> queries[MAX * 2];

int build(int l, int r){
    if(l == r) {
        ++timerNodes;
        queries[timerNodes].emplace_back(-2 * h[l], l);
        return timerNodes;
    }
    int mid = l + r >> 1, cur = ++timerNodes;
    ln[cur]=  build(l, mid);
    rn[cur] = build(mid + 1, r);
    queries[cur]=  queries[ln[cur]];
    merge_sort(queries[cur], queries[rn[cur]]);
    return cur;
}

void solve(int l, int r, int cur){
    if(l == r) {
        lines[cur].emplace_back(h[l], h[l] * h[l] + dp[l] - w[l]);
        return;
    }

    int mid = l + r >> 1;
    solve(l, mid, ln[cur]);
    convex_hull_trick cht;
    for(auto d : lines[ln[cur]]) cht.add(d.a, d.b);
    for(auto [slope, i] : queries[rn[cur]]){
        dp[i] = min(dp[i], cht.query(slope) + w[i - 1] + h[i] * h[i]);
    }

    solve(mid + 1, r, rn[cur]);

    lines[cur] = lines[ln[cur]];
    merge_sort(lines[cur], lines[rn[cur]]);
}

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    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];

    for(int i = 2; i <= N; ++i) dp[i] = inf;
    int root = build(1, N);
    solve(1, N, root);

    cout << dp[N] << '\n';

    return 0;
}

Compilation message (stderr)

building.cpp: In function 'int build(int, int)':
building.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int mid = l + r >> 1, cur = ++timerNodes;
      |               ~~^~~
building.cpp: In function 'void solve(int, int, int)':
building.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for(auto [slope, i] : queries[rn[cur]]){
      |              ^

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