Submission #36588

#	Time	Username	Problem	Language	Result	Execution time	Memory
36588		cheater2k	Aliens (IOI16_aliens)	C++14	100 / 100	229 ms	7588 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

struct ConvexHullTrick {
	// slopes are different from each other
	struct Line {
		long long a; long long b; int id; // b <= 1e12, a >= -2e6
		// id is the ID of the corresponding segment, which is useful for tracing
		Line(long long a=0, long long b=0, int id=0): a(a), b(b), id(id) {}
	};
	deque<Line> L;

	ConvexHullTrick() { L.clear(); }

	bool bad(Line l1, Line l2, Line l3) {
		return 1LL * (l1.b - l3.b) * (l2.a - l1.a) < 1LL * (l1.b - l2.b) * (l3.a - l1.a); // ~ [-2e18, 2e18]
	}
	void add(long long a, long long b, int id) {
		Line d = Line(a, b, id);
		while(L.size() >= 2 && bad(L[L.size()-2], L[L.size()-1], d)) L.pop_back();
		L.push_back(d);
	}
	long long func(Line &d, long long &x) {
		return 1LL * d.a * x + d.b;
	}
	pair<long long,int> get(long long x) {
		while(L.size() >= 2 && func(L[0], x) > func(L[1], x)) L.pop_front(); // L[0] is not good anymore
		return make_pair(func(L[0], x), L[0].id); // get the minimum ID
	}
} cht;

namespace Solver {
	const int N = 100005;
	pair<int, int> inp[N]; // input segments
	int l[N], r[N]; // leftmost and rightmost points of the segments
	int n, m, k;
	long long dp[N];
	int trace[N];

	void process() { // build new segments
		// no segment is contained by another segment
		sort(inp, inp + n, [&](pair<int,int> x, pair<int,int> y) {
			return x.fi < y.fi || (x.fi == y.fi && x.se > y.se);
		});
		int rmax = -1;
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			if (rmax < inp[i].se) {
				rmax = inp[i].se;
				++cnt;
				l[cnt] = inp[i].fi;
				r[cnt] = inp[i].se;
			}
		}
		n = cnt; // 1-based index now
	}

	int check(long long cost) {
		// reset
		cht = ConvexHullTrick();
		memset(dp, 0, sizeof dp);
		memset(trace, 0, sizeof trace);

		// dp[i] = (dp[j-1] - (max(0, r[j-1] - l[j]) ^ 2) + l[j] ^ 2) + (-2 * l[j]) * r[i] + r[i] ^ 2 (j <= i)

		// solve
		cht.add(-2 * l[1], 1LL * l[1] * l[1], 0);
		for (int i = 1; i <= n; ++i) {
			pair<long long, int> g = cht.get(r[i]);
			dp[i] = g.fi + 1LL * r[i] * r[i] + cost;
			trace[i] = g.se;
			long long cur = dp[i] - (1LL * max(0, r[i] - l[i+1]) * max(0, r[i] - l[i+1])) + 1LL * l[i+1] * l[i+1]; // b
			cht.add(-2 * l[i+1], cur, i);
		}

		// trace
		int pos = n, cnt = 0;
		while(pos) ++cnt, pos = trace[pos];
		return cnt;
	}

	long long solve() {
		process();
		// for (int i = 1; i <= n; ++i) {
		// 	printf("l[%d] = %d, r[%d] = %d\n", i, l[i], i, r[i]);
		// }

		long long l = 0, r = 1e13; // cost is positive
		while(l < r) {
			long long mid = ((l + r) >> 1);
			if (check(mid) <= k) r = mid; else l = mid + 1;
		}
		check(l);
		return dp[n] - l * k;
	}
};

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	// init
	Solver::n = n;
	Solver::m = m; // square: [0...m-1][0...m-1]
	Solver::k = k;
	for (int i = 0; i < n; ++i) {
		if (r[i] > c[i]) swap(r[i], c[i]); // [r,c] is the corresponding segment in the diagonal
		Solver::inp[i].fi = r[i];
		Solver::inp[i].se = ++c[i];
	}

	// solve
	return Solver::solve();
}

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