oj.uz

Submission #945739

# Submission time Handle Problem Language Result Execution time Memory
945739 2024-03-14T07:10:43 Z 12345678 Building Bridges (CEOI17_building) C++17
100 / 100
 41 ms 7516 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

#define ll long long

ll n, h[nx], sm, w[nx];

struct line
{
    ll m, c;
    line(ll m, ll c): m(m), c(c){}
    ll val(ll x) {return m*x+c;}
};

struct lichaotree
{
    struct node
    {
        line a;
        node *l, *r;
        node(line a):a(a), l(0), r(0) {}
    };
    typedef node* pnode;
    pnode rt;
    void update(int l, int r, pnode &t, line nw)
    {
        if (!t) return t=new node(nw), void();
        int md=(l+r)/2;
        int ls=nw.val(l)<t->a.val(l);
        int ms=nw.val(md)<t->a.val(md);
        int rs=nw.val(r)<t->a.val(r);
        if (ms) swap(t->a, nw);
        if (l==r) return;
        if (ls^ms) update(l, md, t->l, nw);
        if (ms^rs) update(md+1, r, t->r, nw);
    }
    ll query(int l, int r, pnode t, int x)
    {
        if (!t) return LLONG_MAX;
        if (l==r) return t->a.val(x);
        int md=(l+r)/2;
        if (x<=md) return min(t->a.val(x), query(l, md, t->l, x));
        else return min(t->a.val(x), query(md+1, r, t->r, x));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>h[i];
    for (int i=1; i<=n; i++) cin>>w[i], sm+=w[i];
    s.update(0, 1e6, s.rt, line(-2*h[1], h[1]*h[1]-w[1]));
    //c.add(-2*h[1], h[1]*h[1]-w[1]);
    for (int i=2; i<=n-1; i++)
    {
        ll tmp=s.query(0, 1e6, s.rt, h[i])+h[i]*h[i]-w[i];
        //cout<<i<<' '<<tmp<<'\n';
        //ll tmp=c.query(h[i])+h[i]*h[i]-w[i];
        s.update(0, 1e6, s.rt, line(-2*h[i], h[i]*h[i]+tmp));
        //c.add(-2*h[i], tmp+h[i]*h[i]);
    }
    cout<<s.query(0, 1e6, s.rt, h[n])+h[n]*h[n]-w[n]+sm;
    //cout<<c.query(h[n])+h[n]*h[n]-w[n]+sm;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3136 KB Output is correct
2 Correct 34 ms 3164 KB Output is correct
3 Correct 41 ms 3164 KB Output is correct
4 Correct 33 ms 2908 KB Output is correct
5 Correct 25 ms 4648 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 35 ms 3136 KB Output is correct
7 Correct 34 ms 3164 KB Output is correct
8 Correct 41 ms 3164 KB Output is correct
9 Correct 33 ms 2908 KB Output is correct
10 Correct 25 ms 4648 KB Output is correct
11 Correct 31 ms 3284 KB Output is correct
12 Correct 33 ms 3164 KB Output is correct
13 Correct 25 ms 3144 KB Output is correct
14 Correct 33 ms 3420 KB Output is correct
15 Correct 29 ms 7516 KB Output is correct
16 Correct 24 ms 4432 KB Output is correct
17 Correct 12 ms 2908 KB Output is correct
18 Correct 11 ms 2904 KB Output is correct