oj.uz

Submission #35827

# Submission time Handle Problem Language Result Execution time Memory
35827 2017-12-01T06:29:18 Z funcsr Building Bridges (CEOI17_building) C++14
60 / 100
 3000 ms 38928 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]);
    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 13 ms 38928 KB Output is correct
2 Correct 9 ms 38928 KB Output is correct
3 Correct 3 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 38928 KB Output is correct
2 Correct 506 ms 38928 KB Output is correct
3 Correct 506 ms 38928 KB Output is correct
4 Correct 213 ms 38928 KB Output is correct
5 Correct 2626 ms 38928 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 38928 KB Output is correct
2 Correct 9 ms 38928 KB Output is correct
3 Correct 3 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 506 ms 38928 KB Output is correct
7 Correct 506 ms 38928 KB Output is correct
8 Correct 506 ms 38928 KB Output is correct
9 Correct 213 ms 38928 KB Output is correct
10 Correct 2626 ms 38928 KB Output is correct
11 Correct 409 ms 38928 KB Output is correct
12 Correct 1046 ms 38928 KB Output is correct
13 Correct 129 ms 38928 KB Output is correct
14 Correct 903 ms 38928 KB Output is correct
15 Execution timed out 3000 ms 38928 KB Execution timed out
16 Halted 0 ms 0 KB -