Submission #56854

#	Time	Username	Problem	Language	Result	Execution time	Memory
56854		kingpig9	Aliens (IOI16_aliens)	C++11	4 / 100	7 ms	4812 KiB

aliens

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

ll sqr (ll x) {
	return x * x;
}

template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}

template<class T>
void setmax (T &a, T b) {
	if (a < b) {
		a = b;
	}
}

int N, M, K;
int mxy[MAXM];
ll X[MAXN], Y[MAXN];

//line: 
struct line {
	ll m, b;
	int id;
	line (ll _m, ll _b, int _id) : m(_m), b(_b), id(_id) {}
	ll val (ll x) const {
		return m * x + b;
	}

#warning Is using fraction really enough? Or will it possibly
	pll intersect (const line &a) const {
		//careful, might have to change to double
		pll p(b - a.b, a.m - m);
		if (p.se < 0) {
			p.fi *= -1;
			p.se *= -1;
		}
		return p;
	}
};

int compare (pll p1, pll p2) {
	//p1.fi * p2.se, p1.se * p2.fi
#warning do we need int128 here to compare? int128 might not even be supported in some places
	ll ltval = p1.fi * p2.se, rtval = p1.se * p2.fi;
	if (ltval < rtval) {
		return -1;
	} else if (ltval == rtval) {
		return 0;
	} else {
		return 1;
	}
}

struct convex {
	vector<line> hull;
	int ptr;
	ll x;
	convex() : hull(), ptr(), x(LLONG_MIN) {}
	void clear() {
		hull.clear();
		ptr = 0;
		x = LLONG_MIN;
	}
	void insert (line t) {
		if (hull.empty()) {
			hull.push_back(t);
			return;
		}
		line bk = hull.back();
		assert(bk.m <= t.m);
		if (bk.m == t.m && t.b <= bk.b) {
			return;
		}
		bool curerase = false;
		while (hull.size() >= 2) {
			int hsiz = hull.size();
			line l2 = hull[hsiz - 2];
			pll ph = l2.intersect(hull.back()), pt = l2.intersect(t);
			if (compare(pt, ph) <= 0) {
				if (hsiz == ptr + 1) {
					curerase = true;
				}
				hull.pop_back();
			} else {
				break;
			}
		}
		if (curerase) {
			ptr = int(hull.size()) - 1;
		}
		hull.push_back(t);
	}
	line query (ll t) {
		assert(t >= x);
		for (; ptr + 1 < hull.size(); ptr++) {
			if (hull[ptr].val(t) > hull[ptr + 1].val(t)) {
				break;
			}
		}
		x = t;
		return hull[ptr];
	}
} cht;

ll dp[MAXN];
int use[MAXN];

void moo (ll cost) {
	cht.clear();

	dp[0] = 0;
	use[0] = 0;

	for (int i = 1; i <= N; i++) {
		cht.insert(line(2 * X[i], -(sqr(X[i]) + dp[i - 1]), i - 1));
		line lq = cht.query(Y[i]);
		dp[i] = sqr(Y[i]) - lq.val(Y[i]) + cost;
		if (i != N) {
			dp[i] -= sqr(max(0ll, Y[i] - X[i + 1]));
		}

		use[i] = use[lq.id] + 1;
	}
}

ll take_photos (int nnn, int mmm, int kkk, vector<int> rrr, vector<int> ccc) {
	N = nnn;
	M = mmm;
	K = kkk;

	//R, C
	fillchar(mxy, -1);
	for (int i = 0; i < N; i++) {
		int x = rrr[i], y = ccc[i];
		if (x > y) {
			swap(x, y);
		}
		setmax(mxy[x], y);
	}

	N = 0;
	for (int x = 0; x < M; x++) {
		int y = mxy[x];
		if (y == -1) {
			continue;
		}

		if (N == 0 || Y[N] < y) {
			N++;
			X[N] = x - 1;	//better for the algebra.
			Y[N] = y;
		}
	}

	setmin(K, N);	//IMPORTANT!!! Note: N is adjusted. Therefore, it may not be true that K <= N -- need to do it again.
	ll lo = 0, hi = 2e12;
	while (hi - lo > 1) {
		ll mid = (lo + hi) / 2;
		moo(mid);
		if (use[N] <= K) {
			hi = mid;
		} else {
			lo = mid;
		}
	}

	moo(hi);
	//debug("hi = %lld. use[N] = %d\n", hi, use[N]);
	return dp[N] - hi * K;
}

Compilation message (stderr)

aliens.cpp:48:2: warning: #warning Is using fraction really enough? Or will it possibly [-Wcpp]
 #warning Is using fraction really enough? Or will it possibly
  ^~~~~~~
aliens.cpp:62:2: warning: #warning do we need int128 here to compare? int128 might not even be supported in some places [-Wcpp]
 #warning do we need int128 here to compare? int128 might not even be supported in some places
  ^~~~~~~
aliens.cpp: In member function 'line convex::query(ll)':
aliens.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; ptr + 1 < hull.size(); ptr++) {
          ~~~~~~~~^~~~~~~~~~~~~

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