Submission #259995

#	Time	Username	Problem	Language	Result	Execution time	Memory
259995		ipaljak	Aliens (IOI16_aliens)	C++14	60 / 100	110 ms	8676 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<

using llint = long long;

const llint INF = 1e12;

int n, m, k;
vector<pair<int, int>> I, P;
vector<llint> A, B;
vector<int> hull;

struct Event {
  int x, type, id;
  Event() {}
  Event(int x, int type, int id) : x(x), type(type), id(id) {}
  friend bool operator<(const Event &A, const Event &B) {
    if (A.x == B.x) return A.type < B.type;
    return A.x < B.x;
  }
};

vector<pair<int, int>> get_intervals(int n, const vector<int> &r,
                                     const vector<int> &c) {
  vector<Event> e;
  for (int i = 0; i < n; ++i) {
    int lo = min(r[i], c[i]);
    int hi = max(r[i], c[i]);
    e.emplace_back(lo, 0, i);
    e.emplace_back(hi, 1, i);
  }

  sort(e.begin(), e.end());
  multiset<int> ms;
  vector<pair<int, int>> ret;

  for (const auto &p : e) {
    if (p.type == 0) {
      ms.insert(p.x);
      continue;
    }
    int lo = min(r[p.id], c[p.id]);
    ms.erase(ms.find(lo));
    if (ms.empty() || *ms.begin() > lo) ret.emplace_back(lo, p.x);
  }

  return ret;
}

// y = ax + b = cx + d
// x(a - c) == d - b
double intersect(pair<llint, llint> &A, pair<llint, llint> &B) {
  return (double) (B.second - A.second) / (A.first - B.first);
}

void replace(stack<pair<llint, llint>> &src, stack<pair<llint, llint>> &dest) {
  while (!src.empty()) {
    if (dest.size() < 3) {
      dest.push(src.top());
      src.pop();
      continue;
    }
    pair<llint, llint> A, B, C;
    while (dest.size() >= 3) {
      B = dest.top(); dest.pop();
      A = dest.top();
      C = src.top();
      if (intersect(A, C) < intersect(B, C))
        continue;
      dest.push(B);
      break;
    }
    dest.push(C);
    src.pop();
  }
}


llint ccw(int i, int j, int k) {
  return A[i] * (B[j] - B[k]) + A[j] * (B[k] - B[i]) + A[k] * (B[i] - B[j]);
}

void insert(int x, int *t) {
  while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), x) > 0)
    hull.pop_back();
  hull.push_back(x);
  if (*t >= (int)hull.size()) *t = (int)hull.size() - 1;
}

pair<llint, int> dp(llint cost) {
  vector<llint> f(n, 0);
  vector<int> cnt(n, 0);
  hull.clear();
  A.resize(n, 0); B.resize(n, 0);
  int t = 0;
  for (int i = 0; i < n; ++i) {
    llint c = (llint) I[i].second * I[i].second + cost;
    llint x = (llint) I[i].second;
    f[i] = INF;
    cnt[i] = -1;
    for (; t < (int) hull.size(); ++t) {
      llint a = A[hull[t]], b = B[hull[t]];
      if (c + a * x + b > f[i]) { --t; break; }
      if (c + a * x + b == f[i]) {
        cnt[i] = min(cnt[i], cnt[hull[t]] + 1);
      } else {
        f[i] = c + a * x + b;
        cnt[i] = cnt[hull[t]] + 1;
      }
    }
    t = min((int) hull.size() - 1, t);
    t = max(0, t);
    llint single =
        (llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1) +
        cost;
    if (single < f[i]) {
      f[i] = single;
      cnt[i] = 1;
    }
    A[i] = -2LL * (I[i + 1].first - 1);
    B[i] = f[i] + (llint)(I[i + 1].first - 1) * (I[i + 1].first - 1) -
           (llint)max(0, I[i].second - I[i + 1].first + 1) *
               max(0, I[i].second - I[i + 1].first + 1);
    insert(i, &t);
  }
  return {f[n - 1], cnt[n - 1]};
}

llint take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
  n = nn; m = mm; k = kk;
  for (int i = 0; i < n; ++i) P.emplace_back(r[i], c[i]);
  I = get_intervals(n, r, c);
  n = (int)I.size();
  I.emplace_back(1e9, 1e9);

  k = min(k, n);
  llint lo = 0, hi = (llint) 2 * m * m;
  while (lo < hi) {
    llint mid = (lo + hi) / 2;
    auto val = dp(mid);
    if (val.second > k) lo = mid + 1; else hi = mid;
  }

  auto sol = dp(lo);
  dp(lo - 1);
  return sol.first - (llint) k * lo;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 40