Submission #639647

#	Time	Username	Problem	Language	Result	Execution time	Memory
639647		pls33	Aliens (IOI16_aliens)	C++17	60 / 100	2094 ms	364496 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;

using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;
using fl80_t = long double;

template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;
#pragma endregion

struct line_t
{
    int64_t k, m, p;
    bool operator<(const line_t &o) const { return k < o.k; }
    bool operator<(int64_t x) const { return p < x; }
    long long eval(long long x) const { return k * x + m; }
};

struct cht_t
{
    deque<line_t> hull;

    int64_t div(int64_t a, int64_t b)
    {
        return floor(double(a) / b);
    }

    bool intersect(line_t &x, const line_t &y)
    {
        if (x.k == y.k)
        {
            x.p = x.m > y.m ? INT64_MAX : INT64_MIN;
        }
        else
        {
            x.p = div(y.m - x.m, x.k - y.k);
        }

        return x.p >= y.p;
    }

    void add(long long k, long long m)
    {
        line_t line = {k, m, 0};

        // wtf?
        while (hull.size() >= 2 &&
               (intersect(line, hull.back()),
                intersect(hull.back(), hull[(int)hull.size() - 2]),
                line.p < hull.back().p))
        {
            hull.pop_back();
        }

        hull.push_back(line);
    }

    int64_t query(int64_t x)
    {
        if (!hull.size())
        {
            return INT64_MAX;
        }
        while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x))
        {
            hull.pop_front();
        }

        return hull[0].eval(x);
    }
};

void insert(int64_t left, int64_t tiles, cht_t &cht)
{
    int64_t slope = 2 - 2 * left;
    int64_t offset = (left - 1) * (left - 1) + tiles;

    cht.add(slope, offset);
}

int64_t query(int64_t val, cht_t &cht)
{
    int64_t y = cht.query(val);

    return (y == INT64_MAX) ? INT64_MAX : y + val * val;
}

int64_t cost(p64 range)
{
    assert(range.first <= range.second);
    return (range.second - range.first + 1) * (range.second - range.first + 1);
}

long long take_photos(int n, int m, int k, vi32 r, vi32 c)
{
    vp32 range(n);
    for (int i = 0; i < n; i++)
    {
        if (c[i] > r[i])
        {
            swap(c[i], r[i]);
        }
        range[i] = {c[i], r[i]};
    }

    sort(range.begin(), range.end(),
         [](p32 a, p32 b)
         {
             return (a.first == b.first) ? a.second > b.second : a.first < b.first;
         });

    int cur_max = -1;
    vp32 selected;
    for (auto &r : range)
    {
        if (r.second > cur_max)
        {
            selected.push_back(r);
            cur_max = r.second;
        }
    }

    vvi64 tile(selected.size(), vi64(k + 1, INT64_MAX));
    vector<cht_t> cht(k + 1);
    tile[0][1] = cost(selected[0]);
    insert(selected[0].first, 0, cht[1]);

    for (size_t point = 1; point < tile.size(); point++)
    {
        for (size_t count = 1; count <= min(point + 1, size_t(k)); count++)
        {
            int64_t &cur = tile[point][count];
            int64_t &prev = tile[point - 1][count - 1];
            p32 a = selected[point];
            p32 b = selected[point - 1];

            cur = min(cur, query(a.second, cht[count]));
            if (prev != INT64_MAX)
            {
                int64_t val = prev + cost(a);
                if (a.first <= b.second)
                {
                    val -= cost({a.first, b.second});
                }

                cur = min(cur, val);
            }

            if (cur != INT64_MAX)
            {
                int64_t tiles = tile[point - 1][count - 1];
                if (a.first <= b.second)
                {
                    tiles -= cost({a.first, b.second});
                }

                insert(a.first, tiles, cht[count]);
            }
        }
    }

    int64_t result = *min_element(tile.back().begin(), tile.back().end());
    return result;
}

Compilation message (stderr)

aliens.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
aliens.cpp:57: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   57 | #pragma endregion
      |

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