Submission #903947

#	Time	Username	Problem	Language	Result	Execution time	Memory
903947		Flan312	Building Bridges (CEOI17_building)	C++17	0 / 100	51 ms	7008 KiB

building

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
const ll oo = 1e18;
int n;
ll h[nmax], w[nmax], dp[nmax];
struct segment
{
    ll a, b;
    segment(ll a = 0, ll b = oo) : a(a), b(b) {}
};
struct node
{
    segment line;
    node *l, *r;
    node(const segment &line = segment(), node *l = nullptr, node *r = nullptr) : line(line), l(l), r(r) {}
};
#define check(x) if (x == nullptr) x = new node()
node *lichao = new node();
ll get(const segment &line, int x)
{
    return line.a * x + line.b;
}
void update(node *root, int l, int r, int u, int v, const segment &line)
{
    if (l > v || r < u) return;
    int mid = l + r >> 1;
    if (l >= u && r <= v)
    {
        check(root -> l);
        check(root -> r);
        //6 case, lichao min
        ll rootL = get(root -> line, l);
        ll rootR = get(root -> line, r);
        ll rootM = get(root -> line, mid);
        ll lineL = get(line, l);
        ll lineR = get(line, r);
        ll lineM = get(line, mid);
        if (rootL <= lineL && rootR <= lineR) return;
        if (rootL >= lineL && rootR >= lineR) {root -> line = line; return;}
        if (rootL <= lineL && rootM <= lineM)
        {
            update(root -> r, mid + 1, r, u, v, line);
            return;
        }
        if (rootL >= lineL && rootM >= lineM)
        {
            update(root -> r, mid + 1, r, u, v, root -> line);
            root -> line = line;
            return;
        }
        if (get(root -> line, mid + 1) <= get(line, mid + 1) && rootR <= lineR)
        {
            update(root -> l, l, mid, u, v, line);
            return;
        }
        if (get(root -> line, mid + 1) >= get(line, mid + 1) && rootR >= lineR)
        {
            update(root -> l, l, mid, u, v, root -> line);
            root -> line = line;
            return;
        }
    }
    update(root -> l, l, mid, u, v, line);
    update(root -> r, mid + 1, r, u, v, line);
}
void update(int u, int v, const segment &line) {update(lichao, 1, 2e6, 1, 2e6, line);}
ll get(node *root, int l, int r, int x)
{
    if (root == nullptr || (l > x || r < x)) return oo;
    ll res = get(root -> line, x);
    if (l == r) return res;
    int mid = l + r >> 1;
    res = min(res, get(root -> l, l, mid, x));
    res = min(res, get(root -> r, mid + 1, r, x));
    return res;
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    for (int i = 1; i <= n; ++i)
        cin >> w[i];;
    dp[1] = -w[1];
    update(1, 2e6, segment(-2 * h[1], 1ll * h[1] * h[1] + dp[1]));
    for (int i = 2; i <= n; ++i)
    {
        dp[i] = 1ll * h[i] * h[i] - w[i] + get(lichao, 1, 2e6, h[i]);
        update(1, 2e6, segment(-2 * h[i], 1ll * h[i] * h[i] + dp[i]));
    }
    cout << dp[n] + accumulate(w + 1, w + n + 1, 0LL);
}

Compilation message (stderr)

building.cpp: In function 'void update(node*, int, int, int, int, const segment&)':
building.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'long long int get(node*, int, int, int)':
building.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'int main()':
building.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:31: note: in expansion of macro 'nx'
   90 |     if (ifstream(task".inp")) nx
      |                               ^~
building.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:31: note: in expansion of macro 'nx'
   90 |     if (ifstream(task".inp")) nx
      |                               ^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40