oj.uz

Submission #1051215

# Submission time Handle Problem Language Result Execution time Memory
1051215 2024-08-10T00:12:56 Z turneja Building Bridges (CEOI17_building) C++14
100 / 100
 57 ms 74404 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);

const int L = 0, R = 1e6 + 5;

const int N = 1e5 + 5;
const int MAX = 3e6;
const long long INF = 2e18;

long long a[N];
long long w[N];
long long dp[N];

struct Line {
    long long k, b;
    long long f(long long x) {
        return k * x + b;
    }
    Line(long long k, long long b) : k(k), b(b) {}
};

struct Node {
    Line line;
    int left;
    int right;
    Node(Line line) : line(line), left(-1), right(-1) {}
    Node() : line(0, INF), left(-1), right(-1) {}
};

Node nodes[MAX];
int idx = 0;

void add(int l, int r, int lq, int rq, int node, Line cur) {
    if (l > r || l > rq || r < lq) {
        return;
    }
    int mid = (l + r) / 2;
    if (r - l == 1 && mid == r) {
        mid--;
    }
    if (l >= lq && r <= rq) {
        bool lf = cur.f(l) < nodes[node].line.f(l);
        bool md = cur.f(mid) < nodes[node].line.f(mid);
        if (md) {
            swap(nodes[node].line, cur);
        }
        if (l == r) {
            return;
        }
        if (lf != md) {
            if (nodes[node].left == -1) {
                nodes[node].left = idx;
                nodes[idx++] = Node(cur);
            } else {
                add(l, mid, lq, rq, nodes[node].left, cur);
            }
        } else {
            if (nodes[node].right == -1) {
                nodes[node].right = idx;
                nodes[idx++] = Node(cur);
            } else {
                add(mid + 1, r, lq, rq, nodes[node].right, cur);
            }
        }
        return;
    }
    if (l == r) {
        return;
    }
    if (max(l, lq) <= min(mid, rq)) {
        if (nodes[node].left == -1) {
            nodes[node].left = idx;
            nodes[idx++] = Node();
        }
        add(l, mid, lq, rq, nodes[node].left, cur);
    }
    if (max(mid + 1, lq) <= min(r, rq)) {
        if (nodes[node].right == -1) {
            nodes[node].right = idx;
            nodes[idx++] = Node();
        }
        add(mid + 1, r, lq, rq, nodes[node].right, cur);
    }

    return;
}

long long query(int l, int r, int lq, int rq, int node, long long x) {
    if (l > r || l > rq || r < lq) {
        return INF;
    }
    int mid = (l + r) / 2;
    if (r - l == 1 && mid == r) {
        mid--;
    }
    if (l >= lq && r <= rq) {
        long long ans = nodes[node].line.f(x);
        if (l == r) {
            return ans;
        }
        if (x <= mid && nodes[node].left != -1) {
            ans = min(ans, query(l, mid, lq, rq, nodes[node].left, x));
        }
        if (x > mid && nodes[node].right != -1) {
            ans = min(ans, query(mid + 1, r, lq, rq, nodes[node].right, x));
        }
        return ans;
    }
    long long ans = INF;
    if (max(l, lq) <= min(mid, rq)) {
        if (nodes[node].left == -1) {
            nodes[node].left = idx;
            nodes[idx++] = Node();
        }
        ans = min(ans, query(l, mid, lq, rq, nodes[node].left, x));
    }
    if (max(mid + 1, lq) <= min(r, rq)) {
        if (nodes[node].right == -1) {
            nodes[node].right = idx;
            nodes[idx++] = Node();
        }
        ans = min(ans, query(mid + 1, r, lq, rq, nodes[node].right, x));
    }
    return ans;
}

int main() {
    IOS;
    nodes[idx++] = Node();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    dp[0] = -w[0];
    long long k = -2 * a[0], b = dp[0] + a[0] * a[0];
    Line cur(k, b);
    add(L, R, L, R, 0, cur);
    for (int i = 1; i < n; i++) {
        dp[i] = -w[i] + a[i] * a[i] + query(L, R, L, R, 0, a[i]);
        long long k = -2 * a[i], b = dp[i] + a[i] * a[i];
        Line cur(k, b);
        add(L, R, L, R, 0, cur);
    }
    cout << sum + dp[n - 1];


    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 70748 KB Output is correct
2 Correct 16 ms 70744 KB Output is correct
3 Correct 16 ms 70784 KB Output is correct
4 Correct 16 ms 70748 KB Output is correct
5 Correct 18 ms 70752 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 74068 KB Output is correct
2 Correct 48 ms 74032 KB Output is correct
3 Correct 49 ms 74068 KB Output is correct
4 Correct 48 ms 73976 KB Output is correct
5 Correct 37 ms 74068 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 70748 KB Output is correct
2 Correct 16 ms 70744 KB Output is correct
3 Correct 16 ms 70784 KB Output is correct
4 Correct 16 ms 70748 KB Output is correct
5 Correct 18 ms 70752 KB Output is correct
6 Correct 50 ms 74068 KB Output is correct
7 Correct 48 ms 74032 KB Output is correct
8 Correct 49 ms 74068 KB Output is correct
9 Correct 48 ms 73976 KB Output is correct
10 Correct 37 ms 74068 KB Output is correct
11 Correct 48 ms 74372 KB Output is correct
12 Correct 53 ms 74204 KB Output is correct
13 Correct 43 ms 74332 KB Output is correct
14 Correct 57 ms 74404 KB Output is correct
15 Correct 37 ms 74064 KB Output is correct
16 Correct 38 ms 74064 KB Output is correct
17 Correct 31 ms 74072 KB Output is correct
18 Correct 33 ms 74068 KB Output is correct