Submission #979789

#	Time	Username	Problem	Language	Result	Execution time	Memory
979789		vjudge1	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 100000;
template <typename T>
T square(T x) { return x * x; }

struct linear_fn
{
    int64_t m, t, c;
    linear_fn(int64_t m_, int64_t t_, int64_t c_) { m = m_, t = t_, c = c_; }
    int64_t operator()(int64_t x) { return m * x + t; }
    bool intersects_earlier(linear_fn const &g, linear_fn const &h)
    {
        return (double)(h.t - t) / (m - h.m) < (double)(g.t - t) / (m - g.m);
    }
};

pair<int64_t, int64_t> a[N];

pair<int64_t, int64_t> cht(size_t n, int64_t lambda)
{
    deque<linear_fn> q;
    q.emplace_back(-2 * a[0].first, square(a[0].first) - 2 * a[0].first + 1 + lambda, 0);
    for (size_t i = 0; i < n; ++i)
    {
        while (q.size() >= 2 && q[0](a[i].second) > q[1](a[i].second))
            q.pop_front();
        int64_t x = q[0](a[i].second) + square(a[i].second) + 2 * a[i].second;
        if (i == n - 1)
            return {x, q[0].c + 1};
        linear_fn f(-2 * a[i + 1].first, x - square(max<int64_t>(0, a[i].second - a[i + 1].first + 1)) + square(a[i + 1].first) - 2 * a[i + 1].first + 1 + lambda, q[0].c + 1);
        while (q.size() >= 2 && q[q.size() - 2].intersects_earlier(q.back(), f))
            q.pop_back();
        q.push_back(f);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m, k;
    cin >> n >> m >> k;
    for (size_t i = 0; i < n; ++i)
        cin >> a[i].first >> a[i].second, a[i] = make_pair(min(a[i].first, a[i].second), max(a[i].first, a[i].second));
    sort(a, a + n, [](auto const &u, auto const &v)
         { return u.first == v.first ? u.second > v.second : u.first < v.first; });
    size_t h = 0, l = 0;
    while (h < n)
    {
        while (h < n && a[h].second <= a[l].second)
            ++h;
        ++l;
        if (h < n)
            a[l] = a[h];
    }

    int64_t u = 0, v = m * m;
    while (u < v)
    {
        int64_t lambda = (u + v) / 2;
        auto const [objective_val, cnt] = cht(l, lambda);
        if (cnt > k)
            u = lambda + 1;
        else
            v = lambda;
    }
    auto const [objective_val, cnt] = cht(l, u);
    cout << objective_val - k * u << '\n';
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:65:17: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, const std::pair<long int, long int> >::type' {aka 'const long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if (cnt > k)
      |             ~~~~^~~
aliens.cpp: In function 'std::pair<long int, long int> cht(size_t, int64_t)':
aliens.cpp:23:22: warning: control reaches end of non-void function [-Wreturn-type]
   23 |     deque<linear_fn> q;
      |                      ^
/usr/bin/ld: /tmp/ccV38TBg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpwI2Xj.o:aliens.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccV38TBg.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