Submission #1264980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264980		aeg	Building Bridges (CEOI17_building)	C++20	100 / 100	61 ms	64584 KiB

building

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

constexpr int MAXN = 1e6 + 1;

struct segtr {
  struct fn {
    int h, w;
    int operator()(int h2) { return (h - h2) * (h - h2) + w; }
    fn() : h(1e9), w(0) {}
    fn(int hinit, int winit) : h(hinit), w(winit) {}
  };

  vector<fn> tree;

  segtr(int hinit, int winit) : tree(MAXN << 2, {(int)1e9, 0}) {
    tree[1] = {hinit, winit};
  }

  void add_line(fn nw, int ind = 1, int l = 0, int r = MAXN - 1) {
    int m = (l + r) >> 1;
    bool lef = nw(l) < tree[ind](l);
    bool mid = nw(m) < tree[ind](m);
    if (mid)
      swap(nw, tree[ind]);
    if (r == l)
      return;
    else if (mid != lef)
      add_line(nw, ind << 1, l, m);
    else
      add_line(nw, ind << 1 | 1, m + 1, r);
  }

  int get(int h, int ind = 1, int l = 0, int r = MAXN - 1) {
    int m = (l + r) >> 1;
    if (r == l)
      return tree[ind](h);
    else if (h <= m)
      return min(tree[ind](h), get(h, ind << 1, l, m));
    else
      return min(tree[ind](h), get(h, ind << 1 | 1, m + 1, r));
  }

  void add(int h, int w) {
    w += get(h);
    add_line({h, w});
  }
};

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  vector<int> h(n), w(n);
  for (auto &x : h)
    cin >> x;
  for (auto &x : w)
    cin >> x;

  int cost = 0;
  for (auto x : w)
    cost += x;

  segtr tree(h[0], -w[0]);
  for (int i = 1; i < n - 1; i++)
    tree.add(h[i], -w[i]);

  cost += -w[n - 1] + tree.get(h[n - 1]);
  cout << cost << '\n';
}

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