Submission #363703

#	Time	Username	Problem	Language	Result	Execution time	Memory
363703		saleh	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	384 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
 
#define int long long
#define sz(x) ((int)x.size())
#define mp make_pair
 
using namespace std;
 
const int INF = LLONG_MAX, MAXN = 100 * 1000 + 2;
 
struct line {
	mutable long double a, z;
	mutable long double f;
	mutable int ind;
	bool operator < (const line& x) const { return a < x.a; }
	bool operator < (int x) const { return f < x; }
};

long double ot(line x, line y) { return 1. * (y.z - x.z) / (x.a - y.a); }

struct lc : multiset<line, less<>> {
	bool tabe (iterator x, iterator y) {
		if (y == end()) return x -> f = INF, false;
		if (x -> a == y -> a) x -> f = ((x -> z > y -> z)? INF : -INF);
		else x -> f = ot(*x, *y);
		return x -> f >= y -> f;
	}
	void add(long double x, long double y, int ind) {
		auto nxt = insert({x, y, INF, ind}), h = nxt++, t = h;
		while (tabe(h, nxt)) nxt = erase(nxt);
		if (t != begin() && tabe(--t, h)) tabe(t, h = erase(h));
		while ((h = t) != begin() && (--t) -> f >= h -> f) tabe(t, erase(h));
	}
	void operator += (lc x) {
		if (x.size() > size()) swap(x);
		for (auto i : x) add(i.a, i.z, i.ind);
		x.clear();
	}
	pair<int, int> get(int x) {
		auto l = lower_bound(x);
		return {l -> a * x + l -> z, l -> ind};
	}
};
 
int chi[MAXN];
long double dp[MAXN];
 
long long take_photos(int32_t nn, int32_t mm, int32_t kk, vector<int32_t> l, vector<int32_t> r) {
	int n = nn, m = mm, k = kk;
	long long ans = m * m;
	auto f = [&](long double x) -> int {
		lc s;
		dp[0] = (r[0] - l[0] + 1) * (r[0] - l[0] + 1);
		s.add(2 * l[0], -(dp[0] + l[0] * l[0] + 2 * l[0] + 1), 0);
		for (int i = 1; i < n; i++) {
			auto cho = s.get(r[i]);
			dp[i] = cho.first + r[i] * r[i] + 2 * r[i] + x;
			chi[i] = chi[cho.second] + 1;
			s.add(2 * l[i], -(dp[i] + l[i] * l[i] + 2 * l[i] + 1), i);
		}
		return chi[n - 1];
	};
	for (int i = 0; i < n; i++) if (r[i] < l[i]) swap(r[i], l[i]);
	vector<int> a(n);
	iota(a.begin(), a.end(), 0);
	sort(a.begin(), a.end(), [&](int x, int y) { return mp(l[x], r[x]) < mp(l[y], r[y]); });
	long double dw = 0, up = m * m + 1;
	for (int i = 0; i < 100; i++) {
		long double mid = (dw + up) / 2;
		if (f(mid) > k) up = mid;
		else dw = mid;
	}
	f(dw);
//	cout << ans;
    return ans;
}






/*
int32_t main() {
	
	return 0;
}*/

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