Submission #799063

#	Time	Username	Problem	Language	Result	Execution time	Memory
799063		NothingXD	Aliens (IOI16_aliens)	C++17	100 / 100	162 ms	14108 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out() {cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, m, k; 
pll dp[maxn];
ll x[maxn], y[maxn], z[maxn];
vector<pll> p;

struct CHT{
	static const ll inf = 1e18;
	int l, r;
	vector<pll> a;
	CHT(int _n){
		a.resize(_n);
		l = r = 0;
	}
	ll insec(int l1, int l2){
		assert(x[l1] != x[l2]);
		if (x[l1] > x[l2]) swap(l1, l2);
		return (y[l1] - y[l2] + (y[l1] <= y[l2]? 0: 1) * (x[l2] - x[l1] - 1)) / (x[l2] - x[l1]);
	}
	void add(int idx){
		ll tmp;
		while(r){
			tmp = insec(a[r-1].S, idx);
			//debug(tmp);
			if (x[a[r-1].S] * tmp + y[a[r-1].S] == x[idx] * tmp + y[idx] && z[a[r-1].S] < z[idx]) tmp++;
			if (tmp <= a[r-1].F) r--;
			else break;
		}
		if (!r) a[r++] = {-inf, idx};
		else a[r] = {tmp, idx}, r++;
		//debug(r-1, a[r-1].F, a[r-1].S);
	}
	pll get(ll tmp){
		while(l + 1 < r && a[l+1].F <= tmp) l++;
		return MP(x[a[l].S] * tmp + y[a[l].S], z[a[l].S]);
	}
};

pll Calc(ll lan){
	//debug(lan);
	CHT cht(n);
	dp[0] = {(p[0].S - p[0].F) * (p[0].S - p[0].F) + lan, 1};
	x[0] = -p[0].F;
	y[0] = p[0].F * p[0].F;
	z[0] = 0;
	//debug(x[0], y[0], z[0]);
	//debug(dp[0].F, dp[0].S);
	cht.add(0);
	for (int i = 1; i < n; i++){
		/*dp[i] = {(p[i].S-p[0].F) * (p[i].S-p[0].F) + lan, 1};
		for (int j = 1; j <= i; j++){
			dp[i] = min(dp[i], MP(dp[j-1].F + (p[i].S-p[j].F)*(p[i].S-p[j].F) - (p[j-1].S > p[j].F? (p[j-1].S-p[j].F) * (p[j-1].S-p[j].F): 0) + lan, dp[j-1].S + 1));
		}*/
		x[i] = -p[i].F;
		y[i] = dp[i-1].F + p[i].F * p[i].F - (p[i-1].S > p[i].F? (p[i-1].S-p[i].F)*(p[i-1].S-p[i].F): 0);
		z[i] = dp[i-1].S;
		//debug(x[i], y[i], z[i]);
		cht.add(i);
		pll val = cht.get(2*p[i].S);
		dp[i] = {val.F + (p[i].S) * (p[i].S) + lan, val.S+1};
		//debug(i, dp[i].F, dp[i].S);
	}
	return dp[n-1];
}

const int maxa = 1e6 + 10;
int mx[maxa];

long long take_photos(int _n, int _m, int _k, std::vector<int> R, std::vector<int> C) {
	/*CHT cht(n);
	x[0] = ;
	y[0] = 2;
	x[1] = 10;
	y[1] = 15;
	return cht.insec(0, 1);*/
	memset(mx, -1, sizeof mx);
	n = _n, m = _m, k = _k;
	for (int i = 0; i < n; i++){
		if (R[i] > C[i]) swap(R[i], C[i]);
		mx[R[i]] = max(mx[R[i]], C[i]);
	}
	for (int i = 0; i < m; i++){
		if (mx[i] == -1) continue;
		if (p.empty() || (p.back().S) < mx[i]) p.push_back({i, mx[i]});
	}
	k = min(k, (int)p.size());
	n = p.size();
	for (int i = 0; i < n; i++){
		//debug(i, p[i].F, p[i].S);
		p[i].S++;
	}
	ll l = -1, r = 1e12;
	while(l + 1 < r){
		//debug(l, r);
		ll mid = (l + r) >> 1;
		pll tmp = Calc(mid);
		if (tmp.S <= k) r = mid;
		else l = mid;
	}
	//debug(r);
	pll tmp = Calc(r);
	return tmp.F - r * 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