oj.uz

Submission #964362

# Submission time Handle Problem Language Result Execution time Memory
964362 2024-04-16T17:48:44 Z sheldon Building Bridges (CEOI17_building) C++14
100 / 100
 51 ms 6748 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
     
    struct line {
        long long m, b;
     
        long long eval (long long x) {
            return m * x + b;
        }
    };
     
    struct Node {
        line li;
     
        Node *lchild, *rchild;
     
        Node (line ln) : li (ln), lchild (nullptr), rchild (nullptr) {}
    };
     
    void insert (Node *node, int l, int r, line ln) {
        if (l == r) {
            if (node->li.eval (l) > ln.eval (l)) {
                node->li = ln;
            }
            return;
        }
     
        int mid = (l + r) / 2;
     
        if (node->li.m > ln.m) {
            swap (node->li, ln);
        }
        
        if (ln.eval (mid) < node->li.eval (mid)) {
            swap (node->li, ln);
            if (!node->rchild) {
                node->rchild = new Node (ln);
            } else {
                insert (node->rchild, mid + 1, r, ln);
            }
        } else {
            if (!node->lchild) {
                node->lchild = new Node (ln);
            } else {
                insert (node->lchild, l, mid, ln);
            }
        }
    }
     
    long long query (Node *node, int l, int r, int x) {
        if (l == r) {
            return node->li.eval (l);
        }
     
        int mid = (l + r) / 2;
        if (x <= mid) {
            if (node->lchild)
            return min (node->li.eval (x), query (node->lchild, l, mid, x));
        } else if (node->rchild) {
            return min (node->li.eval (x), query (node->rchild, mid + 1, r, x));
        }
     
        return node->li.eval (x);
    }
     
    void solve() {
        int n;
        cin >> n;
        vector<long long> h (n);
        for (int i = 0; i < n; ++i) {
            cin >> h[i];
        }
        int we;
        cin >> we;
        line li = line {-2 * h[0], -we + h[0] * h[0]};
        Node *root = new Node (li);
        long long pref = we;
        long long ans = 2e18;
        for (int i = 1; i < n; ++i) {
            cin >> we;
            pref += we;
            ans = 1LL * h[i] * h[i] + pref - we + query (root, 0, (int) 1e6 + 5, h[i]);
            insert (root, 0, (int) 1e6 + 5 , line {-2 * h[i], h[i] * h[i] - pref + ans});
        }
        cout << ans;
    }   
     
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        solve();
    }

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1880 KB Output is correct
2 Correct 35 ms 2904 KB Output is correct
3 Correct 37 ms 2904 KB Output is correct
4 Correct 31 ms 2384 KB Output is correct
5 Correct 25 ms 5716 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 39 ms 1880 KB Output is correct
7 Correct 35 ms 2904 KB Output is correct
8 Correct 37 ms 2904 KB Output is correct
9 Correct 31 ms 2384 KB Output is correct
10 Correct 25 ms 5716 KB Output is correct
11 Correct 51 ms 6484 KB Output is correct
12 Correct 44 ms 6228 KB Output is correct
13 Correct 33 ms 3164 KB Output is correct
14 Correct 45 ms 6224 KB Output is correct
15 Correct 25 ms 6748 KB Output is correct
16 Correct 25 ms 5724 KB Output is correct
17 Correct 21 ms 2264 KB Output is correct
18 Correct 22 ms 2260 KB Output is correct