Submission #121392

#	Time	Username	Problem	Language	Result	Execution time	Memory
121392		youngyojun	Aliens (IOI16_aliens)	C++11	0 / 100	4 ms	1920 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define befv(V) ((V)[sz(V)-2])
#define upmin(a,b) (a)=min((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
ll pw(ll n) { return n*n; }
ll operator * (const pll &a, const pll &b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }

const int MAXN = 100055;

struct CHT {
	pll P[MAXN];
	int I[MAXN], n, pv;

	void init() { n = pv = 0; }
	void push(ll a, ll b, int c) {
		pll p(a, b);
		for(; 1 < n && 0 < ccw(P[n-2], P[n-1], p); n--);
		P[n] = p;
		I[n] = c;
		n++;
	}
	ll f(int i, ll X) { return P[i].first * X + P[i].second; }
	pil get(ll X) {
		if(n <= pv) pv = n-1;
		for(ll nw, nxt; pv+1 < n; pv++) {
			nw = f(pv, X); nxt = f(pv+1, X);
			if(nw <= nxt) break;
		}
		return pil(I[pv], f(pv, X));
	}
} cht;

ll C[MAXN], D[MAXN];
int E[MAXN];

int X[MAXN], Y[MAXN];

int N, M, K;

void push(int i) { cht.push(-2ll*X[i], D[i-1] + pw(X[i]) - C[i] - 2ll*X[i], i); }
int f(ll L) {
	cht.init();
	for(int i = 1; i <= N; i++) {
		push(i);
		pil ret = cht.get(Y[i]);
		E[i] = E[ret.first-1] + 1;
		D[i] = ret.second + pw(Y[i]+1) + L;
	}
	return E[N];
}

ll getAns() {
	{
		vector<pii> V, T;
		for(int i = 1; i <= N; i++) {
			if(X[i] > Y[i]) swap(X[i], Y[i]);
			V.eb(X[i], Y[i]);
		}
		sorv(V);
		for(auto &v : V) {
			int x, y; tie(x, y) = v;
			if(!T.empty() && T.back().first == x) T.back().second = y;
			if(T.empty() || T.back().second < y) T.eb(x, y);
		}
		N = sz(T);
		for(int i = 1; i <= N; i++) tie(X[i], Y[i]) = T[i-1];
	}

	for(int i = 2; i <= N; i++)
		C[i] = pw(max(0, Y[i-1] - X[i] + 1));
	
	ll del = pw(M)+5;
	ll s = 0, e = del*2; for(ll m; s < e;) {
		m = (s+e) >> 1;
		if(K < f(m-del)) s = m+1;
		else e = m;
	}
	f(s-del);
	return D[N] - (s-del)*K;
	//E[N];
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	::N = n;
	::M = m;
	::K = k;
	for(int i = 1; i <= ::N; i++) {
		::X[i] = r[i-1];
		::Y[i] = c[i-1];
	}
	return getAns();
}

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