Submission #383172

#	Time	Username	Problem	Language	Result	Execution time	Memory
383172		noshi91	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

#include "aliens.h"

#include <cstddef>
#include <cstdint>

#include <vector>

namespace n91 {

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

template <class Select, class Update>
void larsch(const std::size_t n, Select select, Update update) {
  using usize = std::size_t;

  class header {
  public:
    usize r;
    usize c;
  };

  class node {
  public:
    std::vector<usize> cols;
    usize prev;

    std::vector<header> tent;
    usize pcnt;
    usize curc;

    node(const usize n) : cols(), prev(0), tent(), pcnt(0), curc(0) {
      cols.reserve(n);
      tent.reserve(n / 2);
    }
  };

  std::vector<node> data;

  {
    usize m = n;
    while (m != 0) {
      data.emplace_back(m);
      m /= 2;
    }
  }

  const auto act = [&](const auto &act, const usize layer,
                       const usize row) -> usize {
    node &t = data[layer];

    if ((row >> layer) % 2 == 0) {
      usize res = t.prev;
      usize idx = t.curc;
      while (idx != t.cols.size()) {
        if (select(row, t.cols[res], t.cols[idx])) {
          res = idx;
        }
        idx += 1;
      }
      t.prev = res;
      return t.cols[res];
    }

    const usize a = [&]() {
      const usize step = static_cast<usize>(1) << layer;
      if (row + step > n) {
        return t.cols.back();
      }
      while (t.curc != t.cols.size()) {
        const usize c = t.cols[t.curc];
        while (t.tent.size() != t.pcnt &&
               select(t.tent.back().r, t.tent.back().c, c)) {
          t.tent.pop_back();
        }
        if (t.tent.size() == t.pcnt) {
          t.tent.push_back({row + step, c});
        } else if (t.tent.back().r + step * 2 <= n) {
          t.tent.push_back({t.tent.back().r + step * 2, c});
        }
        t.curc += 1;
      }
      if (t.pcnt != t.tent.size()) {
        data[layer + 1].cols.push_back(t.tent[t.pcnt].c);
        t.pcnt += 1;
      }
      return act(act, layer + 1, row + step);
    }();

    usize res = t.prev;
    usize idx = t.prev;
    while (t.cols[idx] != a) {
      idx += 1;
      if (select(row, t.cols[res], t.cols[idx])) {
        res = idx;
      }
    }
    t.prev = idx;
    return t.cols[res];
  };

  for (usize i = 0; i != n;) {
    data[0].cols.push_back(i);
    i += 1;
    update(i, act(act, 0, i));
  }
}

} // namespace n91

#include <algorithm>
#include <tuple>
#include <vector>

using int64 = long long;

int64 square(int64 x) { return x * x; }

int64 take_photos(int n, int m, int k, int r[], int c[]) {
  struct point {
    int64 r;
    int64 c;
  };
  std::vector<point> points(n);
  for (int i = 0; i != n; i += 1) {
    if (r[i] < c[i]) {
      points[i] = {r[i], c[i]};
    } else {
      points[i] = {c[i], r[i]};
    }
  }
  std::sort(points.begin(), points.end(), [](const auto &l, const auto &r) {
    if (l.r != r.r) {
      return l.r < r.r;
    } else {
      return l.c > r.c;
    }
  });

  {
    std::vector<point> red;
    for (const auto &p : points) {
      if (red.empty() || red.back().c < p.c) {
        red.push_back(p);
      }
    }
    points = red;
    n = points.size();
  }

  const auto L = [&](int64 lambda) -> int64 {
    const auto c_lambda = [&](int i, int j) -> int64 {
      int64 ret = square(points[j - 1].c + 1 - points[i].r);
      if (i != 0 && points[i - 1].c + 1 - points[i].r > 0) {
        ret -= square(points[i - 1].c + 1 - points[i].r);
      }
      return ret + lambda;
    };

    std::vector<int64> d(n + 1);
    d[0] = 0;
    const auto get = [&](int i, int j) -> int64 {
      return d[j] + c_lambda(j, i);
    };
    const auto select = [&](int i, int j0, int j1) -> bool {
      return get(i, j0) > get(i, j1);
    };
    const auto update = [&](int i, int j) { d[i] = get(i, j); };

    n91::larsch(n, select, update);

    return d[n] - lambda * k;
  };

  int64 l_ = -1;
  int64 r_ = int64(m) * m + 1;
  while (r_ - l_ > 2) {
    int64 ll = (l_ + l_ + r_) / 3;
    int64 rr = (l_ + r_ + r_) / 3;
    if (L(ll) < L(rr)) {
      l_ = ll;
    } else {
      r_ = rr;
    }
  }

  return L((l_ + r_) / 2);
}

Compilation message (stderr)

/tmp/ccWGvNhr.o: In function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status