Submission #732650

#	Time	Username	Problem	Language	Result	Execution time	Memory
732650		sentheta	Aliens (IOI16_aliens)	C++17	4 / 100	6 ms	352 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;

map<pair<Int,Int>,Int> mpcnt;
Int bm, bc;

// Max convex hull trick
// To get minimum cht
// Transform m and c to -m and -c before calling _upd()
// Transform _qry() to -_qry()
struct Line {
	mutable Int m, c, p;
	bool operator<(const Line& o)const{ return m<o.m;}
	bool operator<(Int x)const{return p<x;}
};
struct Cht:multiset<Line, less<>> {
	static const bool MINCHT = 1;
	// (for doubles, use INF = 1/.0, div(a,b) = a/b)
	inline Int div(Int a,Int b){ // floored division
		return a/b - ((a^b)<0 && a%b);
	}
	bool isect(iterator x,iterator y){ // check Intersection
		if(y==end()) return x->p = INF, 0;
		if(x->m==y->m) x->p = x->c > y->c ? INF : -INF;
		else x->p = div(y->c - x->c, x->m - y->m);
		return x->p >= y->p;
	}
	
	void _upd(Int m,Int c){ // insert line m*x+c
		auto z = insert({m,c,0}), y=z++, x=y;
		while(isect(y,z)) z = erase(z);
		if(x!=begin() && isect(--x,y)) isect(x, y=erase(y));
		while((y=x)!=begin() && (--x)->p>=y->p) isect(x, erase(y));
	}
	void upd(Int m,Int c){
		MINCHT ? _upd(-m,-c) : _upd(m,c);
	}

	Int _qry(Int x){ // find maximum m*x+c
		if(empty()) return -INF;
		auto l = *lower_bound(x);
		bm = -l.m; bc = -l.c;
		return l.m*x+l.c;
	}
	Int qry(Int x){
		return MINCHT ? -_qry(x) : _qry(x);
	}
};



const int N = 5e4+5;
const int K = 505;
const int M = 1e6+5;

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;
	mpcnt.clear();

	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);

		// if(!mpcnt.count({m,c})) mpcnt[{m,c}] = INF;
		// mpcnt[{m,c}] = min(mpcnt[{m,c}], cnt[i-1]);

		// cht.upd(m, c);


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

		// if(from0 <= not0){
		// 	dp[i] = from0;
		// 	cnt[i] = 1;
		// }
		// else{
		// 	dp[i] = not0;
		// 	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<<30; J; J/=2){
	// {
		// check cost+J
		solve(cost+J);

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


	solve(cost);
	Int ans = dp[n-1] - cnt[n-1]*cost;
	return ans;
}

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