제출 #529090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529090		Graphter	Aliens (IOI16_aliens)	C++17	100 / 100	1763 ms	14080 KiB

aliens

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl
#define REP(i, n) for (Long i = 0; i < (Long)n; i++)
using namespace std;

typedef long long Long;

//https://contest.yandex.com/ioi/contest/2830/problems/F/

const Long INF = 1e18;

struct Line {
	mutable Long m, b, r, cnt;
	//mx + b, intersect with next line at r (rounded down)
	Line() {}
	Line(Long m, Long b, Long cnt): m(m), b(b) , r(0), cnt(cnt) {}
	bool operator <(const Line &other) const {return m < other.m;}
	bool operator <(const Long &x) const {return r < x;}
	Long getVal(Long x) {return m * x + b;}
};

struct CHT{
	set<Line, less<>> envelope;
	
	Long div(Long a, Long b) { //floored division
		//CAREFUL ! this won't produced the right convex envelope
		//but the maxY function will still work for integers
		//if you need the correct convex envelope, use double division
		return a / b - ((a ^ b) < 0 && a % b); 
	}
	
	Long intersect(Line l1, Line l2) {
		return div(l1.b - l2.b , l2.m - l1.m );
	}
	
	bool bad(Line l1, Line l2, Line l3) {
		//tells if l2 is bad an can be eliminated by l3
		return intersect(l2 , l3) <= intersect(l1, l2);
	}
	
	void addLine(Line L) { //O(log n)
		L.m *= -1;
		L.b *= -1;
		L.r = INF;
		auto it = envelope.lower_bound(L);
		if (it != envelope.end() && it->m == L.m) { //same slope
			if (it->b >= L.b) return;
			else it = envelope.erase(it);
		}
		if (it != envelope.begin()) {
			if (it != envelope.end() && bad(*prev(it), L , *it)) {
				//L is not necessary
				return;
			}
			it--;
			while (it != envelope.begin()) { //left elimination
				if (bad(*prev(it), *it, L)) {
					it = envelope.erase(it);
					it--;
				} else break;
			}
			it->r = intersect(*it, L);
		} 
		it = envelope.upper_bound(L);
		if (it != envelope.end()) {
			while (next(it) != envelope.end()) { //right elimination
				if (bad(L , *it, *next(it))) it = envelope.erase(it);
				else break;
			}
			L.r = intersect(L , *it);
		}
		envelope.insert(L);
	}
	
	pair<Long, Long> minY(Long x) { //O(log n)
		assert(!envelope.empty());
		Line L = *envelope.lower_bound(x);
		return {-L.getVal(x), L.cnt};
	}
};

struct Range {
	int l, r;
	Range(int l, int r): l(l), r(r){}
	bool operator <(const Range &other) {
		return r < other.r;
	}
	bool contains(Range &other) {
		return l <= other.l && other.r <= r;
	}
};

void removeContained(vector<Range> &v) {
	int n = v.size();
	vector<Range> ans = {v.back()};
	for (int i = n - 2; i >= 0; i--) {
		if (ans.back().contains(v[i])) continue;
		ans.push_back(v[i]);
	}
	reverse(ans.begin(), ans.end());
	v = ans;
}

Long square(Long x) {
	return x * x;
}

vector<int> L, R;
Long cost(int l, int r) {
	Long ans = square(R[r] - L[l]);
	if (l > 0) ans -= square(max(0, R[l - 1] - L[l]));
	return ans;
}

pair<Long, Long> getBest(Long lambda, int k) {
	//returns <P(lambda, x), g(x)>
	int n = L.size();
	//if (n == 1) return {square(R[0] - L[0]) - lambda + lambda * k, 1 - k};
	CHT cht;
	vector<Long> dp(n);
	vector<Long> cnt(n);
	auto getLine = [&](int i) {
		return Line(-2 * L[i + 1], 
		dp[i] + square(L[i + 1]) - square(max(0, R[i] - L[i + 1])), cnt[i]);
	};
	
	cht.addLine(Line(- 2 * L[0], + square(L[0]), 0));
	for (int i = 0; i < n; i++) {
		tie(dp[i], cnt[i]) = cht.minY(R[i]);
		dp[i] += square(R[i]) - lambda;
		cnt[i]++;
		if (i + 1 < n) cht.addLine(getLine(i));
	}
	return {dp[n - 1] + lambda * k, cnt[n - 1] - k};
}

bool check(Long lambda, int k) {
	return getBest(lambda, k).second <= 0;
}

const Long INF2 = 1e13;
Long minCost(int k) { //O(logn)
	// T T T ... F F F
	Long low = -INF2;
	Long high = INF2;
	if (check(high, k)) return getBest(high, k).first; //all T
	while (high - low > 1) { 
		Long mid = low + (high - low) / 2;
		if (check(mid, k)) low = mid;
		else high = mid;
	}
	//2 values low -> T and high-> F
	return getBest(low, k).first;
}

Long take_photos(int n, int m, int K, vector<int> x, vector<int> y) {
	vector<Range> v;
	REP(i, n) {
		int l = min(x[i], y[i]);
		int r = max(x[i], y[i]);
		v.push_back({l, r});
	}
	sort(v.begin(), v.end());
	removeContained(v);
	n = v.size();
	L = R = vector<int>(n);
	REP(i, n) {
		v[i].r++;
		L[i] = v[i].l;
		R[i] = v[i].r;
	}
	K = min(K, n);
	return minCost(K);
}
/*
5 8 5
1 5
3 4
2 6
1 4
3 5 
ans = 34

7 30 5
1 5
3 4
2 6
1 4
3 5 
9 15
14 22
ans = 160
*/
/*int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> x(n);
	vector<int> y(n);
	REP(i, n) {
		cin >> x[i] >> y[i];
	}
	cout << take_photos(n, m, k, x, y) << "\n";
	
	return 0;
}
*/

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