oj.uz

Submission #964350

# Submission time Handle Problem Language Result Execution time Memory
964350 2024-04-16T17:21:54 Z sheldon Building Bridges (CEOI17_building) C++14
30 / 100
 42 ms 2908 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 && 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 1 ms 456 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 42 ms 2908 KB Output isn't correct
7 Halted 0 ms 0 KB -