Submission #1081178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081178		erray	Aliens (IOI16_aliens)	C++17	100 / 100	149 ms	7628 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi16d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

typedef __int128_t int128_t;


struct LineContainer {
  using E = array<int64_t, 3>;
  deque<E> d;
  array<int64_t, 2> pass(E x, E y) {
    return {y[1] - x[1], x[0] - y[0]}; //It might be already bigger
  }
  
  void add(int64_t m, int64_t c, int info) {
    E add;
    add[0] = m, add[1] = c, add[2] = info;
    while (int(d.size()) > 1) {
      array<int64_t, 2> isect0 = pass(add, d.back());
      array<int64_t, 2> isect1 = pass(d.back(), d.end()[-2]);
      if (add[1] <= d.back()[1] || int128_t(isect0[0] * isect1[1]) < int128_t(isect1[0] * isect0[1])) {
        d.pop_back();
      } else {
        break;
      }
    }
    d.push_back(add);
    debug(add, d);
  }
  int64_t eval_eq(int64_t m, int64_t c, int64_t x) {
  return m * x + c;
  }
  int64_t eval_element(E e, int64_t x) {
    return eval_eq(e[0], e[1], x);
  }
  pair<int64_t, int> eval(int64_t x) {
    assert(!d.empty());
    while (int(d.size()) > 1 && eval_element(d[0], x) > eval_element(d[1], x)) {
      d.pop_front();
    }
    debug(x, d);
    return {eval_element(d.front(), x), d.front()[2]};
  }
};


int64_t S(int x) {
  return int64_t(x) * x;
}

long long take_photos(int N, int M, int K, std::vector<int> R_, std::vector<int> C) {
  vector<array<int, 2>> ranges;
  for (int i = 0; i < N; ++i) {
    if (R_[i] - C[i] > 0) {
      ranges.push_back({C[i], R_[i] + 1});
    } else {
      ranges.push_back({R_[i], C[i] + 1});
    }
  }
  sort(ranges.begin(), ranges.end(), [&](auto x, auto y) {
    return array<int, 2>{x[0], -x[1]} < array<int, 2>{y[0], -y[1]};
  });
  vector<int> L, R;
  int mx_r = -1;
  for (auto[l, r] : ranges) {
    if (mx_r < r) {
      mx_r = r;
      L.push_back(l);
      R.push_back(r);
    }
  }
  debug(N, L, R);
  N = int(L.size());
  K = min(K, N);
  //cost = best[i][j] + S(R[n] - L[i]) - (n + 1 < N && R[n] > L[n + 1] ? S(R[n] - L[n + 1]) : 0);
  auto Get = [&](int64_t penalty) {
    debug(penalty);
    LineContainer lc;
    vector<pair<int64_t, int>> ans(N);
    lc.add(-2 * L[0], S(L[0]), 0);
    for (int i = 0; i < N; ++i) {
      ans[i] = lc.eval(R[i]);
      ans[i].first += + S(R[i]) - (i + 1 < N && R[i] > L[i + 1] ? S(R[i] - L[i + 1]) : 0) + penalty;
      ans[i].second++;
      debug(ans[i]);
      if (i < N - 1) {
        lc.add(-2 * L[i + 1], ans[i].first + S(L[i + 1]), ans[i].second);
      }
    }
    debug(ans);
    return ans[N - 1];
  };
  
  int64_t low = 0, high = int64_t(M) * M;
  while (low < high) {
    int64_t mid = (low + high) >> 1;
    if (Get(mid).second > K) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  auto[r, k] = Get(low);
  debug(low, r, k);
  r -= 1LL * low * K;
  return r;
}

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