Submission #739518

#	Time	Username	Problem	Language	Result	Execution time	Memory
739518		boris_mihov	Aliens (IOI16_aliens)	C++17	100 / 100	135 ms	6832 KiB

aliens

#include "aliens.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, m, k;
struct Interval
{
    int l, r;
    inline friend bool operator < (const Interval &a, const Interval &b)
    {
        return a.l < b.l || (a.l == b.l && a.r < b.r);
    }
};

struct CHT
{
    struct Line
    {
        llong x, y;
        int cntPenalties;
        int to;

        std::pair <llong,int> getValue(int at)
        {
            return {x * at + y, cntPenalties};
        }
    };

    llong intersect(Line a, Line b)
    {
        if (a.y >= b.y)
        {
            return INF;
        }

        return (b.y - a.y) / (a.x - b.x) - ((b.y - a.y) % (a.x - b.x) == 0 && b.cntPenalties < a.cntPenalties);
    }

    std::deque <Line> dq;
    void reset()
    {
        dq.clear();
    }

    void push(Line toPush)
    {
        while (dq.size() && dq.front().getValue(dq.front().to) > toPush.getValue(dq.front().to))
        {
            dq.pop_front();
        }

        if (dq.empty())
        {
            dq.push_front(toPush);
        } else
        {
            llong where = intersect(toPush, dq.front());
            if (where <= m) dq.push_front({toPush.x, toPush.y, toPush.cntPenalties, where});
        }
    }

    std::pair <llong,int> find(int at)
    {
        while (dq.size() >= 2 && dq[dq.size() - 2].to >= at)
        {
            dq.pop_back();
        }

        assert(dq.size());
        return dq.back().getValue(at);
    }
};

CHT cht;
std::vector <Interval> v;
std::pair <llong,int> dp[MAXN];

std::pair <llong,int> check(llong penalty)
{
    cht.reset();
    cht.push({-2 * v.back().r, 1LL * v.back().r * v.back().r + penalty, 1, m});
    
    for (int idx = v.size() - 1 ; idx >= 0 ; --idx)
    {
        dp[idx] = cht.find(v[idx].l);
        dp[idx].first += 1LL * v[idx].l * v[idx].l;

        if (idx != 0)
        {
            llong toRemove = std::max(0, v[idx - 1].r - v[idx].l); toRemove *= toRemove;
            cht.push({-2 * v[idx - 1].r, 1LL * v[idx - 1].r * v[idx - 1].r + dp[idx].first - toRemove + penalty, dp[idx].second + 1, m});
        }
    }

    return dp[0];
}

llong take_photos(int N, int M, int K, std::vector <int> x, std::vector <int> y) 
{
    n = N; m = M; k = K;
    std::vector <Interval> sorted;
    for (int i = 0 ; i < n ; ++i)
    {
        sorted.push_back({std::min(x[i], y[i]), std::max(x[i], y[i]) + 1});
    }

    std::sort(sorted.begin(), sorted.end());
    for (const Interval &curr : sorted)
    {
        while (v.size() && v.back().l == curr.l && curr.r >= v.back().r)
        {
            v.pop_back();
        }

        if (v.empty() || v.back().r < curr.r)
        {
            v.push_back(curr);
        }
    }

    k = std::min(k, (int)v.size());
    llong l = -1, r = 1LL * m * m, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        auto res = check(mid);
        if (res.second == k)
        {
            return res.first - k * mid;
        }

        if (res.second > k) l = mid;
        else r = mid;
    }
    
    auto resL = check(l);
    auto resR = check(r);    
    llong fL = resL.first - resL.second * l;
    llong fR = resR.first - resR.second * r;
    return fL + (fR - fL) * (resL.second - k) / (resL.second - resR.second);
}

Compilation message (stderr)

aliens.cpp: In member function 'void CHT::push(CHT::Line)':
aliens.cpp:66:85: warning: narrowing conversion of 'where' from 'llong' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |             if (where <= m) dq.push_front({toPush.x, toPush.y, toPush.cntPenalties, where});
      |                                                                                     ^~~~~

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