Submission #618187

#	Time	Username	Problem	Language	Result	Execution time	Memory
618187		Temmie	Aliens (IOI16_aliens)	C++17	100 / 100	1450 ms	69308 KiB

aliens

#include <bits/stdc++.h>

struct Line {
	
	long long a, b;
	int used;
	
	constexpr std::pair <long long, int> f(long long x) const {
		return { a * x + b, used };
	}
	
};

struct LCT {
	
	int size;
	std::vector <std::pair <bool, Line>> lines;
	
	LCT(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		lines.resize(size << 1);
	}
	
	inline void reset() {
		lines.assign(size << 1, { false, { 0, 1LL << 60, 0 } });
	}
	
	inline void insert(Line line) {
		insert(line, 0, 0, size);
	}
	
	void insert(Line line, int now, int l, int r) {
		int mid = (l + r) >> 1;
		bool fl = !lines[now].first || line.f(l) < lines[now].second.f(l);
		bool ml = !lines[now].first || line.f(mid) < lines[now].second.f(mid);
		if (ml) {
			std::swap(line, lines[now].second);
			if (!lines[now].first) {
				lines[now].first = true;
				return;
			}
		}
		if (r <= l + 1) {
			return;
		}
		fl ^ ml ? insert(line, now * 2 + 1, l, mid) : insert(line, now * 2 + 2, mid + 1, r);
	}
	
	inline std::pair <long long, int> query(int x) {
		return query(x, 0, 0, size);
	}
	
	std::pair <long long, int> query(int x, int now, int l, int r) {
		if (!lines[now].first || r <= l + 1) {
			return lines[now].first ? lines[now].second.f(x) : std::make_pair(1LL << 60, 0);
		}
		int mid = (l + r) >> 1;
		return std::min(lines[now].second.f(x), x < mid ? query(x, now * 2 + 1, l, mid) : query(x, now * 2 + 2, mid + 1, r));
	}
	
};

long long take_photos(int n, int m, int k, std::vector <int> _R, std::vector <int> _C) {
	std::vector <std::pair <int, int>> a;
	for (int i = 0; i < n; i++) {
		a.emplace_back(_R[i], _C[i]);
		if (_R[i] > _C[i]) {
			std::swap(a.back().first, a.back().second);
		}
	}
	std::sort(a.begin(), a.end(), [] (std::pair <int, int> u, std::pair <int, int> v) {
		return u.first == v.first ? u.second > v.second : u.first < v.first;
	});
	int furth = -1;
	for (int i = 0; i < n; i++) {
		if (a[i].second > furth) {
			furth = a[i].second;
			a.emplace_back(a[i]);
		}
	}
	a.erase(a.begin(), a.begin() + n);
	n = a.size();
	LCT lct(m);
	auto f = [&] (long long mid, int& used) -> long long {
		lct.reset();
#define add(val, use, poi) lct.insert({ (poi + 1) * -2, val + (long long) (poi + 1) * (poi + 1), use });
		add(0, 0, a.back().second);
		long long res = 0;
		for (int i = n - 1; ~i; i--) {
			std::pair <long long, int> now = lct.query(a[i].first);
			used = now.second + 1;
			res = now.first + mid + (long long) a[i].first * a[i].first;
			if (i) {
				res -= (long long) (a[i - 1].second + 1 - a[i].first) * (a[i - 1].second + 1 - a[i].first) * (a[i].first <= a[i - 1].second);
				add(res, used, a[i - 1].second);
			}
		}
		return res;
	};
	long long l = 0, r = 1LL << 60, best = 0;
	while (l <= r) {
		long long mid = (l + r) >> 1;
		int used;
		f(mid, used);
		if (used > k) {
			l = best = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return f(best, furth) - best * 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