Submission #732504

#	Time	Username	Problem	Language	Result	Execution time	Memory
732504		sentheta	Aliens (IOI16_aliens)	C++17	25 / 100	66 ms	456 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 = 1e16;

// Max Lichao Tree
// To get minimum cht, set value of `MINCHT`
const Int L = -1e7-5;
const Int R = 1e7+5;
#define mid ((tl+tr)>>1)
struct Cht{
	static const bool MINCHT = 1;
	// evaluate y=p*x+q at x=b
	inline Int eval(pii a,Int b){return a.ff*b + a.ss; }
	V<pii> st={{0,-INF}};
	V<Int> lc={-1}, rc={-1};
	Int make(){
		st.push_back({0,-INF}); lc.push_back(-1); rc.push_back(-1);
		return st.size()-1;
	}

	void _upd(pii a,Int v=0,Int tl=L,Int tr=R){
		if(eval(a,mid) > eval(st[v],mid)) swap(a, st[v]);
		if(eval(a,tl) > eval(st[v],tl)){
			if(lc[v]==-1) lc[v] = make(), st[lc[v]] = st[v];
			_upd(a, lc[v],tl,mid);
		}
		if(eval(a,tr) > eval(st[v],tr)){
			if(rc[v]==-1) rc[v] = make(), st[rc[v]] = st[v];
			_upd(a, rc[v],mid+1,tr);
		}
	}
	void upd(pii a){
		MINCHT ? _upd({-a.ff,-a.ss}) : _upd(a);
	}
	void upd(Int m,Int c){upd({m,c});}

	Int _qry(Int x,Int v=0,Int tl=L,Int tr=R){
		if(v==-1) return -INF;
		if(tl==tr) return eval(st[v],x);
		if(x <= mid) return max(eval(st[v],x), _qry(x, lc[v],tl,mid));
		else return max(eval(st[v],x), _qry(x, rc[v],mid+1,tr));
	}
	Int qry(Int x){
		return MINCHT ? -_qry(x):_qry(x);
	}
} cht;
#undef mid



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

int n, m, k;

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



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

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

	// // dp[0][p]
	// rep(p,1,k+1) dp[0][p] = sqr(r[0]-l[0]+1);
	// dp[i][0]
	rep(i,0,n) dp[i][0] = INF;

	rep(pp,1,k+1){
		int p = pp&1;
		// dbg(p);

		dp[0][p] = sqr(r[0]-l[0]+1);
		rep(i,1,n){
			// dp[i][p] = sqr(r[i]-l[0]+1);
			// rep(j,1,i+1) dp[i][p] = min(dp[i][p],
			// 	dp[j-1][p^1] +sqr(r[i]-l[j]+1) -(l[j]<=r[j-1] ? sqr(r[j-1]-l[j]+1):0)
			// );

			if(l[i] <= r[i-1]){
				cht.upd(-2*l[i], l[i]*l[i]-2*l[i] +dp[i-1][p^1] -sqr(r[i-1]-l[i]+1));
			}
			else{
				cht.upd(-2*l[i], l[i]*l[i]-2*l[i] +dp[i-1][p^1]);
			}

			dp[i][p] = r[i]*r[i] +2*r[i] +1 +cht.qry(r[i]);
			dp[i][p] = min(dp[i][p], sqr(r[i]-l[0]+1));
			// dbg(dp[i][p]);
		}
	}


	Int ans = dp[n-1][k&1];
	return ans;
}

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