Submission #657848

#	Time	Username	Problem	Language	Result	Execution time	Memory
657848		benjaminkleyn	Aliens (IOI16_aliens)	C++17	100 / 100	799 ms	15752 KiB

aliens

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


struct Line 
{
	mutable ll k, m, p, cnt;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> 
{
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) 
    {
		return a / b - ((a ^ b) < 0 && a % b); 
    }

	bool isect(iterator x, iterator y) 
    {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}

	void add(ll k, ll m, ll cnt) 
    {
		auto z = insert({k, m, 0, cnt}), y = z++, x = y;

		while (isect(y, z)) 
            z = erase(z);

		if (x != begin() && isect(--x, y)) 
            isect(x, y = erase(y));

		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}

	pair<ll,ll> query(ll x) 
    {
		assert(!empty());
		auto l = lower_bound(x);
		return {l->k * x + l->m, l->cnt};
	}
} cht;

#define COL first
#define ROW second

vector<pair<ll,ll>> pts, dp;

pair<ll,ll> calc(int n, ll cost)
{
    dp[0] = {0, 0};
    cht.clear();
    for (int i = 1; i <= n; i++)
    {
        ll gradient = - 2 * (pts[i].ROW - 1);
        ll square = (pts[i].ROW - 1);
        ll overlap = max(pts[i - 1].COL - pts[i].ROW + 1, 0LL);
        cht.add(-gradient, -(dp[i - 1].first + square * square - overlap * overlap + cost), dp[i - 1].second);

        pair<ll,ll> res = cht.query(pts[i].COL);
        dp[i] = {-res.first + pts[i].COL * pts[i].COL, res.second + 1};
    }

    return dp[n];
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    vector<pair<ll,ll>> temp_pts(n);
    for (int i = 0; i < n; i++)
    {
        if (r[i] > c[i])
            swap(r[i], c[i]);
        temp_pts[i] = {c[i], r[i]};
    }
    sort(temp_pts.begin(), temp_pts.end());

    pts.push_back({-1, -1});
    for (pair<ll,ll> pt : temp_pts)
    {
        while (pts.size() && pts.back().ROW >= pt.ROW)
            pts.pop_back();
        pts.push_back(pt);
    }

    n = pts.size() - 1;
    dp.resize(n + 1);

    ll lo = 0, hi = 1e12, res = 1e12, mid;
    while (lo <= hi)
    {
        mid = (lo + hi) / 2;

        calc(n, mid);

        if (dp[n].second <= k)
            hi = mid - 1, res = mid;
        else
            lo = mid + 1;

    }

    calc(n, res);
    return dp[n].first - k * res;
}

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