Submission #380560

#	Time	Username	Problem	Language	Result	Execution time	Memory
380560		hoaphat1	Aliens (IOI16_aliens)	C++17	100 / 100	1354 ms	16660 KiB

aliens

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

struct node {
	long long a, b;
	int id;
	node(long long a = 0, long long b = 1e18, int id = 0) : a(a), b(b), id(id) {
	}
	pair<long long, int> get(int x) {
		return make_pair(a * x + b, id);
	}
};

struct Eins {
	vector<node> st;
	vector<int> b;
	int n;
	Eins(vector<int>& b) : b(b) {
		n = (int) b.size();
		st.resize(n << 2 | 1);
	}
	void modify(int id, int l, int r, node val) {
		int mid = l + r >> 1;
		if (val.get(b[mid]) < st[id].get(b[mid])) swap(val, st[id]);
		if (l == r) return ;
		if (val.get(b[l]) < st[id].get(b[l])) modify(id << 1, l, mid, val);
		if (val.get(b[r]) < st[id].get(b[r])) modify(id << 1|1, mid + 1, r, val);
	}
	pair<long long, int> get(int id, int l, int r, int x) {
		auto ans = st[id].get(x);
		if (l == r) return ans;
		int mid = l + r >> 1;
		if (x <= b[mid]) return min(get(id << 1, l, mid, x), ans);
		return min(get(id << 1|1, mid + 1, r, x), ans);
	}
};

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	vector<pair<int,int>> a;
	for (int i = 0; i < n; i++) {
		if (r[i] < c[i]) swap(r[i], c[i]);
		a.emplace_back(r[i], c[i]);
	}
	sort(a.begin(), a.end());
	vector<pair<int,int>> b;
	for (int i = 0; i < n; i++) {
		while (!b.empty() && b.back().second >= a[i].second) b.pop_back();
		b.push_back(a[i]);
	}
	swap(a, b);
	n = (int) a.size();
	auto test = [&](long long c) {
		const long long inf = 1e18;
		vector<pair<long long, int>> dp(n + 1, make_pair(inf, 0));
		dp[0] = {0, 0};
		vector<int> b;
		for (int i = 0; i < n; i++) {
			b.push_back(a[i].first);
		}
		sort(b.begin(), b.end());
		b.resize(unique(b.begin(), b.end()) - b.begin());
		Eins Tree(b);
		/*
			dp i = dp j + c + sq a[i-1].f - (a[j].s-1) = sq x - 2*x*(aj.s-1) + sq (aj.s-1)
		*/
		Tree.modify(1, 0, Tree.n - 1, node(-2 * (a[0].second - 1), c + 1ll * (a[0].second - 1) * (a[0].second - 1), 0));
		for (int j = 1; j <= n; j++) {
			/*for (int from = j; from > 0; from--) {
				/*long long pre = (from > 1 ? a[from - 2].first : -1);
				if (pre >= a[from - 1].second) pre = (pre - a[from - 1].second + 1) * (pre - a[from - 1].second + 1);
				else pre = 0;
				int pre = from > 1 ? a[from - 2].first : -1;
				pre = max(0, pre - a[from - 1].second + 1);
				dp[j] = min(dp[j], {dp[from - 1].first + 1ll * (a[j - 1].first - a[from - 1].second + 1) * (a[j - 1].first - a[from - 1].second + 1) + c - 1ll * pre * pre, dp[from - 1].second + 1});
			}*/
			auto x = Tree.get(1, 0, Tree.n - 1, a[j-1].first);
			dp[j] = make_pair(x.first + 1ll * a[j-1].first * a[j-1].first, x.second + 1);
			int pre = max(0, a[j-1].first - a[j].second + 1);
			if (j < n) Tree.modify(1, 0, Tree.n - 1, node(-2 * (a[j].second - 1), dp[j].first + c + 1ll * (a[j].second - 1) * (a[j].second - 1) - 1ll * pre * pre, dp[j].second));
		}
		return dp[n];
	};
	long long l = 0, R = 1ll * m * m, ans = -1;
	while (l <= R) {
		long long mid = l + R >> 1;
		if (test(mid).second <= k) {
			ans = mid;
			R = mid - 1;
		}
		else l = mid + 1;
	}
	assert(ans !=- 1);
	return test(ans).first - ans * k;
}
 /*
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << take_photos(2, 7, 1, {2,3}, {3,4});
}*/

Compilation message (stderr)

aliens.cpp:70:5: warning: "/*" within comment [-Wcomment]
   70 |     /*long long pre = (from > 1 ? a[from - 2].first : -1);
      |      
aliens.cpp: In member function 'void Eins::modify(int, int, int, node)':
aliens.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid = l + r >> 1;
      |             ~~^~~
aliens.cpp: In member function 'std::pair<long long int, int> Eins::get(int, int, int, int)':
aliens.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid = l + r >> 1;
      |             ~~^~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   long long mid = l + R >> 1;
      |                   ~~^~~

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