Submission #129573

#	Time	Username	Problem	Language	Result	Execution time	Memory
129573		Deemo	Aliens (IOI16_aliens)	C++14	100 / 100	481 ms	7788 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second
#define count joiasdfh

const int MAXN = 1e5 + 100;
const int MAXM = 1e6 + 10;
const ll INF = (ll)2e18 + 10;

int n;
vector<pii> segs;
ll dp[MAXN], b[MAXN], sl[MAXN];
int count[MAXN];

void conv(int id, bool fl = false){
	if (!fl)
		b[id] = b[id]*MAXN + count[id], sl[id] *= MAXN;
	else
		b[id] /= MAXN, sl[id] /= MAXN;
}

ll meet(int i, int j){
	ll x = b[j] - b[i];
	ll y = sl[i] - sl[j];
	if (y < 0)
		x = -x, y = -y;
	return (x + (y-1))/ y;
}

int sec[MAXN];
ll best[MAXN];
pair<int, ll> getOpt(ll C){
	memset(dp, 63, sizeof(dp));
	dp[0] = 0;
	b[0] = 1ll*(segs[0].F-1)*(segs[0].F-1);
	sl[0] = -2ll*(segs[0].F-1);
	conv(0);
	int sz = 0;
	best[sz] = -INF;
	sec[sz++] = 0;

	for (int i = 1; i <= n; i++){
		{
			int pos = upper_bound(best, best + sz, segs[i-1].S) - best-1;
			int j = sec[pos];
			conv(j, true);
			dp[i] = b[j] + sl[j]*segs[i-1].S + 1ll*segs[i-1].S*segs[i-1].S + C;
			conv(j);
			count[i] = count[j] + 1;
		}
		if (i == n) break;

		ll temp = max(0, segs[i-1].S-segs[i].F + 1);
		b[i] = dp[i]+1ll*(segs[i].F-1)*(segs[i].F-1)-temp*temp;
		sl[i] = -2*(segs[i].F-1);
		conv(i);
		while (sz > 1 && meet(i, sec[sz-1]) <= meet(sec[sz-1], sec[sz-2])) sz--;
		best[sz] = meet(sec[sz-1], i);
		sec[sz++] = i;
	}
	return {count[n], dp[n] - C*count[n]};
}

long long take_photos(int _n, int m, int k, std::vector<int> r, std::vector<int> c) {
	n = _n;
	segs.clear();
	for (int i = 0; i < n; i++) {
		if (r[i] > c[i])
			swap(r[i], c[i]);
		segs.push_back({r[i], c[i]});
	}
	sort(segs.begin(), segs.end());
	vector<pii> temp;
	for (auto s: segs){
		while (temp.size() && temp.back().F == s.F)
			temp.pop_back();
		if (temp.empty() || s.S > temp.back().S)
			temp.push_back(s);
	}
	segs = temp;
	n = segs.size();

	k = min(n, k);
	ll lo = 0, hi = 1ll*m*m;
	while (hi - lo > 1){
		ll mid = hi+lo>>1;
		auto res = getOpt(mid);
		if (res.F <= k)
			hi = mid;
		else
			lo = mid;
	}
	auto resL = getOpt(hi);
	auto resR = getOpt(lo);
	if (resR.F <= k)
		return resR.S;
	ll dif = (resL.S-resR.S)/ (resR.F - resL.F);
	return resL.S - dif*(k - resL.F);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:93:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid = hi+lo>>1;
            ~~^~~

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