Submission #53055

#	Time	Username	Problem	Language	Result	Execution time	Memory
53055		kingpig9	Aliens (IOI16_aliens)	C++11	4 / 100	6 ms	4640 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];

ll dp[MAXN];
int use[MAXN];
pii hull[MAXN];	//pii(start of interval, which index does it become optimal?)
int hl, hr;

ll getval (int a, int b) {
	ll newarea = sqr(Y[b] - X[a] + 1);
	if (a > 1 && Y[a - 1] >= X[a]) {
		newarea -= sqr(Y[a - 1] - X[a] + 1);
	}
	return dp[a - 1] + newarea;
}

void moo (ll cost) {
	hl = hr = 0;
	for (int i = 0; i <= N; i++) {
		if (i == 0) {
			dp[0] = 0;
			use[0] = 0;
			hull[hr++] = {1, 1};
		} else {
			while (hl < hr - 1 && hull[hl + 1].se <= i) {
				hl++;
			}
			
			int pind = hull[hl].se;
			use[i] = use[pind - 1] + 1;
			dp[i] = getval(pind, i) + cost;

			if (i == N) {
				break;
			}

			int optind = -1;
			while (hl != hr) {
				//when is getval(i + 1, ind) <= getval(hull.back().fi, ind)?
				int start1 = hull[hr - 1].fi;
				int start2 = i + 1;

				if (getval(start1, N) <= getval(start2, N)) {
					//optimization...
					optind = N + 1;
					break;
				}

				int lo = start2 - 1, hi = N + 1;	//hi is definitely true. lo is def not true
				while (hi - lo > 1) {
					int mid = (lo + hi) / 2;
					//only difference here: inequality needs to be strict -- that was the issue :P
					if (getval(start1, mid) > getval(start2, mid)) {
						hi = mid;
					} else {
						lo = mid;
					}
				}

				optind = hi;
				if (optind <= hull[hr - 1].se) {
					hr--;
				} else {
					break;
				}
			}

			if (optind <= N) {
				hull[hr++] = {i + 1, optind};
			}
		}
	}
}

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;
			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 = -1, hi = 2e12;

	while (hi - lo > 1) {
		ll mid = (lo + hi) / 2;
		moo(mid);
		if (use[N] > K) {
			lo = mid;
		} else {
			hi = mid;
		}
	}

	moo(hi);
	return dp[N] - hi * K;
}

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