Submission #259897

#	Time	Username	Problem	Language	Result	Execution time	Memory
259897		ipaljak	Aliens (IOI16_aliens)	C++14	60 / 100	2001 ms	8824 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 int MAXN = 5e4 + 5;
const llint INF = 1e17;

vector<pair<int, int>> I, P;

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 take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
  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);

  vector<llint> dp_prev(n, 0), dp_curr(n, 0);
  stack<pair<llint, llint>> env_prev, env_curr;
  for (int i = 0; i < n; ++i) {
    dp_prev[i] =
        (llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1);
    llint A = -2LL * (I[i + 1].first - 1);
    llint B = dp_prev[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);
    env_curr.push({A, B});
  }

  replace(env_curr, env_prev);

  for (int i = 1; i < k; ++i) {
    int t = 0;
    for (int j = 0; j < n; ++j) {
      llint c = (llint) I[j].second * I[j].second;
      llint x = (llint) I[j].second;
      llint env_a = -INF, env_b = -INF;
      dp_curr[j] = INF;
      while (!env_prev.empty() && t < j) {
        auto p = env_prev.top();
        if (c + p.first * x + p.second <= dp_curr[j]) {
          dp_curr[j] = c + p.first * x + p.second;
          env_a = p.first; env_b = p.second;
          env_prev.pop();
          ++t;
          continue;
        }
        break;
      }
      if (env_a != -INF || env_b != -INF) {
        env_prev.push({env_a, env_b});
        --t;
      }
      dp_curr[j] = min(dp_curr[j], dp_prev[j]);
      llint A = -2LL * (I[j + 1].first - 1);
      llint B = dp_curr[j] +
                (llint)(I[j + 1].first - 1) * (I[j + 1].first - 1) -
                (llint)max(0, I[j].second - I[j + 1].first + 1) *
                    max(0, I[j].second - I[j + 1].first + 1);
      env_curr.push({A, B});
    }
    swap(dp_prev, dp_curr);
    while (!env_prev.empty()) env_prev.pop();
    replace(env_curr, env_prev);
  }

  return dp_prev[n - 1];
}

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