Submission #596761

#	Time	Username	Problem	Language	Result	Execution time	Memory
596761		8e7	Aliens (IOI16_aliens)	C++17	100 / 100	194 ms	8972 KiB

aliens

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);

const ll inf = 1LL<<60;
int siz = 0;		
ll l[maxn], r[maxn];
ll dp[maxn], num[maxn];

struct line{
	ll m, k, cnt;
	line(){m = 0, k = inf, cnt = 0;}
	line(ll a, ll b, ll c){m = a, k = b, cnt = c;}	
	ll val(ll x){return m * x + k;}
};
void solve(ll cost){
	deque<line> deq;		
	deq.push_back(line(-2 * l[1], l[1] * l[1] + cost, 0)); 
	for (int i = 1;i <= siz;i++) {
		while (deq.size() > 1 && deq[0].val(r[i]) >= deq[1].val(r[i])) deq.pop_front();		
		dp[i] = deq[0].val(r[i]) + r[i] * r[i];	
		num[i] = deq[0].cnt + 1;

		//add line
		if (i == siz) continue;
		ll cj = max(0LL, r[i] - l[i+1]);
		cj *= cj;
		line add(-2*l[i+1], l[i+1] * l[i+1] + dp[i] - cj + cost, num[i]);

		auto cdiv = [&] (ll p, ll q){ //ceil
			if (q < 0) p = -p, q = -q;
			if (p < 0) return p / q;
			else return (p + q - 1) / q;
		};
		while (deq.size() > 1) {
			line lef = deq[deq.size()-2], rig = deq.back();
			if (cdiv(add.k - rig.k, rig.m - add.m) <= cdiv(rig.k - lef.k, lef.m - rig.m)) {
				deq.pop_back();	
			} else {
				break;
			}
		}	
		deq.push_back(add);
	}	
}
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
	vector<pii> seg;
	for (int i = 0;i < n;i++) {
		seg.push_back({min(R[i], C[i]), max(R[i], C[i]) + 1});	
	}	
	sort(seg.begin(), seg.end(), [&] (pii x, pii y){return x.ss == y.ss ? x.ff > y.ff : x.ss < y.ss;});
	vector<pii> stk;
	for (int i = 0;i < n;i++) {
		while (stk.size() && seg[i].ff <= stk.back().ff) stk.pop_back();
		stk.push_back(seg[i]);
	}
	siz = stk.size();
	for (int i = 1;i <= siz;i++) {
		l[i] = stk[i-1].ff, r[i] = stk[i-1].ss;	
	}
	ll low = 0, up = 1LL<<40;
	while (low < up - 1) {
		ll mid = (low + up) / 2;
		for (int i = 1;i <= siz;i++) dp[i] = inf, num[i] = 0;	
		num[0] = 0, dp[0] = 0;
		solve(mid);
		if (num[siz] >= k) {
			low = mid;
		} else {
			up = mid;
		}
	}
	for (int i = 1;i <= siz;i++) dp[i] = inf, num[i] = 0;	
	num[0] = 0, dp[0] = 0;
	solve(low);
	return -low * k + dp[siz];
	
}

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