Submission #868298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868298	2023-10-31T03:16:34 Z	phudzctg	Building Bridges (CEOI17_building)	C++14	Compilation error	0 ms	0 KB

building

#include <bits/stdc++.h>
#define N 100001
#define maxx 100000
#define inf 1000000000

using namespace std;
typedef long long ll;
typedef pair<ll, ll> line;
int n, M, h[N], w[N], a[N];
ll dp[N];
ll f(line l, int x) {
    if (l.first == inf && l.second == inf)
        return ll(inf) * inf;
    return l.first * a[x] + l.second;
}
line L[4 * maxn];
void add_line(line nw, int v = 1, int l = 1, int r = M) {
    if (f(nw, l) >= f(L[v], l) && f(nw, r) >= f(L[v], r))
        return;
    if (f(nw, l) <= f(L[v], l) && f(nw, r) <= f(L[v], r)) {
        swap(L[v], nw);
        return;
    }
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(L[v], l);
    bool mid = f(nw, m) < f(L[v], m);
    if(mid)
        swap(L[v], nw);
    if(r - l == 1)
        return;
    else
        if(lef != mid) {
            add_line(nw, 2 * v, l, m);
        } else {
            add_line(nw, 2 * v + 1, m, r);
        }
}

ll get(int x, int v = 1, int l = 1, int r = M) {
    int m = (l + r) / 2;
    if(r - l == 1)
        return f(L[v], x);
    else
        if(x < m)
            return min(f(L[v], x), get(x, 2 * v, l, m));

        else
            return min(f(L[v], x), get(x, 2 * v + 1, m, r));
}
#define task "BUILD"
int main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> h[i];
    for(int i = 1; i <= n; ++i)
        cin >> w[i];

    set<int> tmp;
    for(int i = 1; i <= n; ++i)
        tmp.insert(h[i]);
    M = 0;
    for(int x : tmp)
        a[++M] = x;
    for(int i = 1; i <= n; ++i)
        h[i] = lower_bound(a + 1, a + M + 1, h[i]) - a;

    for(int i = 1; i <= 4 * M; ++i)
        L[i] = make_pair(inf, inf);
    dp[1] = -w[1];
    add_line(make_pair(-2 * a[h[1]], dp[1] + ll(a[h[1]])*a[h[1]]));
    for(int i = 2; i <= n; ++i) {
        dp[i] = ll(a[h[i]]) * a[h[i]] - w[i] + get(h[i]);
        add_line(make_pair(-2 * a[h[i]], dp[i] + ll(a[h[i]])*a[h[i]]));
    }

    ll ans = dp[n];
    for(int i = 1; i <= n; ++i)
        ans += w[i];

    cout << ans;

}

Compilation message

building.cpp:16:12: error: 'maxn' was not declared in this scope; did you mean 'maxx'?
   16 | line L[4 * maxn];
      |            ^~~~
      |            maxx
building.cpp: In function 'void add_line(line, int, int, int)':
building.cpp:18:23: error: 'L' was not declared in this scope
   18 |     if (f(nw, l) >= f(L[v], l) && f(nw, r) >= f(L[v], r))
      |                       ^
building.cpp:20:23: error: 'L' was not declared in this scope
   20 |     if (f(nw, l) <= f(L[v], l) && f(nw, r) <= f(L[v], r)) {
      |                       ^
building.cpp:25:29: error: 'L' was not declared in this scope
   25 |     bool lef = f(nw, l) < f(L[v], l);
      |                             ^
building.cpp: In function 'll get(int, int, int, int)':
building.cpp:42:18: error: 'L' was not declared in this scope
   42 |         return f(L[v], x);
      |                  ^
building.cpp:45:26: error: 'L' was not declared in this scope
   45 |             return min(f(L[v], x), get(x, 2 * v, l, m));
      |                          ^
building.cpp:48:26: error: 'L' was not declared in this scope
   48 |             return min(f(L[v], x), get(x, 2 * v + 1, m, r));
      |                          ^
building.cpp: In function 'int main()':
building.cpp:76:9: error: 'L' was not declared in this scope
   76 |         L[i] = make_pair(inf, inf);
      |         ^
building.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~