제출 #732726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
732726		sentheta	Aliens (IOI16_aliens)	C++17	100 / 100	232 ms	10272 KiB

aliens

#include "aliens.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
#define cerr if(1) cerr

const Int INF = 1e18;
const Int N = 1e5+5;
// const Int K = 505;
const Int M = 1e6+5;


struct line {
	Int m, c;
	int idx;
	Int eval(Int x) { return m * x + c; }
	Int cut(line l) {
		return (c - l.c) / (l.m - m);
	}
};
struct Cht {
	line s[N];
	int st = 1, ed = 0;

	void upd(line cur) {
		while(ed-st+1>=2 && cur.cut(s[ed])<=s[ed].cut(s[ed-1])) --ed;
		s[++ed] = cur;
	}

	line qry(Int x) {
		while(ed-st+1>=2 && s[st].eval(x) > s[st+1].eval(x)) st++;
		return s[st];
	}
};



Int n, m, k;
V<Int> l, r;

Int dp[N], cnt[N];
inline Int sqr(Int x){return x*x;}

void solve(Int cost){
	Cht cht;

	dp[0] = sqr(r[0]-l[0]+1) +cost;
	cnt[0] = 1;

	rep(i,1,n){
		// dp[i] = sqr(r[i]-l[0]+1) +cost;
		// cnt[i] = 1;

		// rep(j,1,i+1){
		// 	Int x = dp[j-1] +sqr(r[i]-l[j]+1) -(l[j]<=r[j-1] ? sqr(r[j-1]-l[j]+1):0) + cost;
		// 	if(x < dp[i]){
		// 		dp[i] = x;
		// 		cnt[i] = cnt[j-1]+1;
		// 	}
		// 	if(x==dp[i]){
		// 		cnt[i] = min(cnt[i], cnt[j-1]+1);
		// 	}
		// }

		Int m = -2*l[i];
		Int c = l[i]*l[i]-2*l[i] +dp[i-1] -(l[i]<=r[i-1] ? sqr(r[i-1]-l[i]+1):0);

		line cur = {m, c, i};
		cht.upd(cur);

		Int from0 = sqr(r[i]-l[0]+1) +cost;
		Int not0 = r[i]*r[i] +2*r[i] +1 +cht.qry(r[i]).eval(r[i]) +cost;

		if(from0 <= not0){
			dp[i] = from0;
			cnt[i] = 1;
		}
		else{
			dp[i] = not0;
			cnt[i] = cnt[cht.qry(r[i]).idx-1] + 1;
			// cnt[i] = mpcnt[{bm,bc}] + 1;
		}
		// dbg(dp[i]);
		// dbg(cnt[i]);
	}
}


Int take_photos(int _n,int _m,int _k,V<int> _l,V<int> _r){
	n = _n; m = _m; k = _k;
	l = V<Int>(all(_l));
	r = V<Int>(all(_r));

	// remove subsegments
	V<int> ord;
	rep(i,0,n){
		if(l[i] > r[i]) swap(l[i], r[i]);
		ord.push_back(i);
	}
	sort(all(ord),[&](int i,int j){
		if(l[i]==l[j]) return r[i] < r[j];
		return l[i] > l[j];
	});
	V<int> stak;
	for(int i : ord){
		while(!stak.empty() && r[stak.back()]<=r[i]) stak.pop_back();
		stak.push_back(i);
	}
	reverse(all(stak));
	ord.swap(stak);
	// result is ordered from l

	// reorder l[] and r[]
	{
		V<Int> vl, vr;
		for(int i : ord){
			// cerr << l[i] _ r[i] << nl;
			vl.push_back(l[i]);
			vr.push_back(r[i]);
		}
		l.swap(vl);
		r.swap(vr);
	}
	n = ord.size();



	// find minimum cost to make <= k merging
	Int cost = -1;
	for(Int J=1LL<<42; J; J/=2){
	// for(Int J=m*m; J; J/=2) rep(loop,0,2){
	// {
		// check cost+J
		solve(cost+J);

		if(cnt[n-1] > k) cost+=J;
		else ;
	}
	cost++;

	// dbg(k);

	solve(cost-1);
	Int a = dp[n-1], b = cnt[n-1];
	Int ans1 = a - b*(cost-1);
	// dbg(cnt[n-1]);

	solve(cost);
	Int c = dp[n-1], d = cnt[n-1];
	Int ans2 = c - d*cost;
	// dbg(cnt[n-1]);


	if(k>=n) return ans2;
	// linear progression from ans1 to ans2
	Int ans = ans1 + (k-b)*(ans2-ans1)/(d-b);
	
	// dbg(k);
	// dbg(cnt[n-1]);
	// assert(cnt[n-1] <= k);
	// Int ans = dp[n-1] - cnt[n-1]*cost;
	return ans;
}

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