Submission #36610

#	Time	Username	Problem	Language	Result	Execution time	Memory
36610		aome	Aliens (IOI16_aliens)	C++14	100 / 100	269 ms	9236 KiB

aliens

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

typedef pair<long long, long long> pll;
typedef pair<int, pll> pill;
const int N = 100005;

void modify(vector<pll> &a) {
	vector<pll> b = a; a.clear();
	sort(b.begin(), b.end(), [&] (pll x, pll y) {
		return (x.first == y.first) ? x.second > y.second : x.first < y.first;
	});
	int mx = 0;
	for (auto i : b) {
		if (mx >= i.second) continue;
		mx = i.second, a.push_back(i);
	}
}

int trace[N];
long long f[N];
long long val[N];
vector<pll> a;
deque<pill> dq;

long long cal(pll x, pll y) {
	return x.first * y.first + x.second + y.second;
}

bool bad(pll x, pll y, pll z) {
	return (x.second - z.second) * (z.first - y.first) >= (y.second - z.second) * (z.first - x.first);
}

void add(pll x, int id) {
	while (dq.size() >= 2 && bad(dq[dq.size() - 2].second, dq[dq.size() - 1].second, x)) dq.pop_back();
	dq.push_back(pill(id, x));
}

void query(pll x, int id) {
	while (dq.size() >= 2 && cal(x, dq[0].second) > cal(x, dq[1].second)) dq.pop_front();
	trace[id] = dq[0].first, f[id] = cal(x, dq[0].second);
}

int solve(long long x) {
	int n = a.size();
	for (int i = 1; i < n; ++i) {
		val[i] = max(0LL, a[i - 1].second - a[i].first), val[i] *= val[i];
	}
	dq.clear();
	for (int i = 1; i <= n; ++i) {
		add(pll(-2 * a[i - 1].first, a[i - 1].first * a[i - 1].first - val[i - 1] + f[i - 1]), i - 1);
		query(pll(a[i - 1].second, a[i - 1].second * a[i - 1].second + x), i);
	}
	int cnt = 0, cur = n;
	while (cur) cnt++, cur = trace[cur];
	return cnt;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {	
	for (int i = 0; i < n; ++i) {
		a.push_back(pll(min(r[i], c[i]), max(r[i], c[i]) + 1));
	}
	modify(a), n = a.size();
	long long lo = 0, hi = 1e12;
	while (lo < hi) {
		long long mid = (lo + hi) >> 1;
		if (solve(mid) <= k) hi = mid; else lo = mid + 1; 
	}
	solve(lo); return f[n] - lo * k;
}

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