Submission #529442

#	Time	Username	Problem	Language	Result	Execution time	Memory
529442		Graphter	Aliens (IOI16_aliens)	C++17	100 / 100	1681 ms	5060 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/

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;
}

struct OptRange {
	int l, r, opt;
	OptRange(int l, int r, int opt): l(l), r(r), opt(opt){}
};

const int MX = 1e5;
pair<int, int> ranges[MX];

Long getBest(Long lambda, int k) {
	int n = L.size();
	vector<Long> dp(n);
	dp[0] = cost(0, 0) - lambda;
	ranges[0] = {1, -1};
	auto getOptimum = [&](int i, int opt) {
		if (opt == -1) return cost(0, i) - lambda;
		assert(opt + 1 <= i);
		return dp[opt] + cost(opt + 1, i) - lambda;
	};
	int head = 0;
	int tail = 0;
	for (int i = 0; i + 1 < n; i++) {
		assert(ranges[head].first == i + 1);
		auto improve = [&](int pos, int opt) {
			return getOptimum(pos, i) < getOptimum(pos, opt);
		};
		int high = n - 1;
		while (head <= tail && improve(ranges[tail].first, ranges[tail].second)) {
			high = ranges[tail].first - 1;
			tail--;
		}
		if (head > tail) {
			ranges[0] = {i + 1, i};
			head = tail = 0;
		} else {
			int low = ranges[tail].first;
			int opt = ranges[tail].second;
			if (!improve(high, opt)) low = high++;
			// F F F ... T T T
			while (high - low > 1) {
				int mid = (low + high) / 2;
				if (improve(mid, opt)) high = mid;
				else low = mid;
			}
			if (high < n) ranges[++tail] = {high, i};
		}
		dp[i + 1] = getOptimum(i + 1, ranges[head].second);
		ranges[head].first++;
		if (tail > head && ranges[head].first >= ranges[head + 1].first) head++;
	}
	return dp[n - 1] + lambda * k;
}

const Long INF2 = 1e13;

Long minCost(int k) { //O(log n)
	Long low = -INF2;
	Long high = INF2;
	while (high - low > 2) {
		Long m1 = low + (high - low) / 3;
		Long m2 = high - (high - low) / 3;
		if (getBest(m1, k) < getBest(m2, k)) low = m1;
		else high = m2;
	}
	Long maxi = getBest(low, k); 
	for (Long i = low + 1; i <= high; i++) {
		maxi = max(maxi, getBest(i, k));
	}
	return maxi;
}

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