Submission #985274

#	Time	Username	Problem	Language	Result	Execution time	Memory
985274		windowwife	Building Bridges (CEOI17_building)	C++17	100 / 100	79 ms	13032 KiB

building

//fully dynamic convex hull trick/ linecontainer practice uwu :3
#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 4;
ll n, h[maxn], w[maxn], tw, dp[maxn];
struct Line
{
    bool type;
    long double i;
    ll x, y;

};
bool operator < (const Line& A, const Line& B)
{
    if (A.type || B.type) return A.i < B.i; //for binary search
    return A.x > B.x; //for the convex hull, change to < if asking for max
}
set<Line> hull;
bool has_prev (set<Line>::iterator it)
{
    return it != hull.begin();
}
bool has_next (set<Line>::iterator it)
{
    return it != hull.end() && next(it) != hull.end();
}
long double isect (set<Line>::iterator A, set<Line>::iterator B)
{
    return (long double)1.0 * (A->y - B->y)/(B->x - A->x);
}
bool check (set<Line>::iterator it)
{
    if (has_next(it) && next(it)->y <= it->y) return false; //it > next(it) for all x
    return !(has_prev(it) && has_next(it) && isect(prev(it), next(it)) <= isect(prev(it), it)); //normal convex hull also have this
}
void change_isect (set<Line>::iterator it)
{
    if (has_prev(it))
    {
        Line l = *it;
        l.i = isect(prev(it), it);
        hull.insert(hull.erase(it), l);
    }
}
void add_line (ll x, ll y)
{
    set<Line>::iterator it;
    //parallel case
    it = hull.lower_bound({0, 0, x, y});
    if (it != hull.end() && it->x == x)
    {
        if (it->y <= y) return; //change to >= if asking for max
        hull.erase(it);
    }
    it = hull.insert({0, 0, x, y}).first;
    if (check(it))
    {
        while (has_prev(it) && !check(prev(it))) hull.erase(prev(it));
        while (has_next(it) && !check(next(it))) hull.erase(next(it));
        if (has_next(it)) change_isect(next(it));
        change_isect(it);
    }
    else hull.erase(it);
}
ll solve (ll q)
{
    Line l = *prev(hull.upper_bound({1, (long double)q, 0, 0}));
    return l.x*q + l.y;
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        tw += w[i];
    }
    dp[1] = -w[1];
    for (int i = 2; i <= n; i++)
    {
        add_line(-2*h[i - 1], dp[i - 1] + h[i - 1]*h[i - 1]);
        dp[i] = h[i]*h[i] - w[i] + solve(h[i]);
    }
    cout << tw + dp[n];
}

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