oj.uz

Submission #35830

# Submission time Handle Problem Language Result Execution time Memory
35830 2017-12-01T06:32:57 Z funcsr Building Bridges (CEOI17_building) C++14
30 / 100
 2193 ms 39520 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(xs) xs.begin(), xs.end()
#define INF (1LL<<60)
#define _1 first
#define _2 second
using namespace std;
#define MAX_N 1000001
int seg[MAX_N+1];
bool is_set[MAX_N+1];

int total = 0;
void add(int i, int v) {
  for (int x=i+1; x<=MAX_N; x+=x&-x) seg[x] += v;
}
int sum(int i) {
  int s = 0;
  for (int x=i+1; x>0; x-=x&-x) s += seg[x];
  return s;
}
int kth(int w) {
  if (w <= 0) return 0;
  int x = 0;
  for (int k=(1<<19); k>0; k/=2) {
    if (x+k <= MAX_N && seg[x+k] < w) {
      w -= seg[x+k];
      x += k;
    }
  }
  return x;
}
inline int p_left(int x) {
  int s = sum(x-1);
  if (s == 0) return -1;
  return kth(s);
}
inline int p_right(int x) {
  int s = sum(x);
  if (s == total) return -1;
  return kth(s+1);
}

int prv[MAX_N*2-1], nxt[MAX_N*2-1];
void set_val(int k, int v) {
  if (v) {
    int a = p_left(k), b = -1;
    if (a != -1) b = nxt[a];
    else b = p_right(k);
    if (a != -1) nxt[a] = k;
    if (b != -1) prv[b] = k;
    nxt[k] = b, prv[k] = a;
  }
  else {
    int a = prv[k], b = nxt[k];
    if (a != -1) nxt[a] = b;
    if (b != -1) prv[b] = a;
    prv[k] = nxt[k] = -1;
  }

  if (v) add(k, 1), total++;
  else add(k, -1), total--;
  is_set[k] = v;
}


typedef pair<int, long long> P;

P operator -(const P &a, const P &b) { return P(a._1-b._1, a._2-b._2); }
inline long long det(P a, P b) { return 1LL*a._1*b._2 - 1LL*a._2*b._1; }

int N;
int H[100000], W[100000];
long long dp[1000001];
long long f[1000001];
inline P get(int x) { return P(x, f[x]); }

void update(int x, long long y) {
  if (dp[x] <= y) return;
  if (dp[x] < INF) if (is_set[x]) set_val(x, 0);
  P p = P(x, y+1LL*x*x);
  dp[x] = y;
  f[x] = p._2;
  while (true) {
    int right = p_right(x);
    if (right == -1) break;
    P r = get(right);
    if (p._2 >= r._2) return; // erase p
    else {
      if (nxt[right] == -1) break;
      P k = get(nxt[right]);
      if (det(r-p, k-r) > 0) break;
      set_val(right, 0);
    }
  }

  while (true) {
    int left = p_left(x);
    if (left == -1) break;
    P l = get(left);
    if (l._2 >= p._2) set_val(left, 0);
    else {
      if (prv[left] == -1) break;
      P k = get(prv[left]);
      if (det(l-k, p-l) > 0) break;
      set_val(left, 0);
    }
  }
  int right = p_right(x);
  if (right != -1 && prv[right] != -1) {
    P r = get(right);
    P l = get(prv[right]);
    if (det(p-l, r-p) <= 0) return;
  }
  set_val(x, 1);
}

signed main() {
  cin >> N;
  rep(i, N) cin >> H[i];
  long long sum = 0;
  rep(i, N) {
    cin >> W[i];
    sum += W[i];
    W[i] = -W[i];
  }
  rep(h, 1000001) dp[h] = INF, f[h] = INF;
  rep(i, MAX_N*2-1) prv[i] = nxt[i] = -1;
  update(H[0], W[0]);
  for (int i=1; i<N-1; i++) {
    long long m = INF;
    int st = kth(1);
    if (st == -1) continue;
    for (int x=st; x!=-1; x=nxt[x]) m = min(m, f[x] - 2LL*x*H[i]);
    //
    vector<P> xs;
    for (int x=st; x!=-1; x=nxt[x]) xs.push_back(get(x));
    rep(i, (int)xs.size()-2) if (det(xs[i+1]-xs[i], xs[i+2]-xs[i]) <= 0) assert(false);
    //
    update(H[i], m+1LL*H[i]*H[i]+W[i]);

  }
  long long m = INF;
  rep(h, 1000001) m = min(m, dp[h] + 1LL*(h-H[N-1])*(h-H[N-1]));
  cout << sum + m + W[N-1] << "\n";
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38928 KB Output is correct
2 Correct 13 ms 38928 KB Output is correct
3 Correct 6 ms 38928 KB Output is correct
4 Correct 9 ms 38928 KB Output is correct
5 Correct 6 ms 38928 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2126 ms 39068 KB Output is correct
2 Correct 2129 ms 39068 KB Output is correct
3 Correct 1963 ms 39068 KB Output is correct
4 Correct 769 ms 38928 KB Output is correct
5 Runtime error 2193 ms 39520 KB Execution timed out (wall clock limit exceeded)

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38928 KB Output is correct
2 Correct 13 ms 38928 KB Output is correct
3 Correct 6 ms 38928 KB Output is correct
4 Correct 9 ms 38928 KB Output is correct
5 Correct 6 ms 38928 KB Output is correct
6 Correct 2126 ms 39068 KB Output is correct
7 Correct 2129 ms 39068 KB Output is correct
8 Correct 1963 ms 39068 KB Output is correct
9 Correct 769 ms 38928 KB Output is correct
10 Runtime error 2193 ms 39520 KB Execution timed out (wall clock limit exceeded)