Submission #1036415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036415		AmirAli_H1	Aliens (IOI16_aliens)	C++17	60 / 100	2025 ms	58752 KiB

aliens

// In the name of Allah
 
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
 
typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;
 
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = (1 << 17) + 4;
const int maxs = 2e6 + 4;
const ll oo = 1e12 + 4;
 
int n, m, k;
pii a[maxn]; vector<pii> A;
vector<int> ls[maxs];
priority_queue<pair<int, pii>> qu;
pll dp[maxn]; ll R; int t[2 * maxn];
 
ll cal(pll a, pll b) {
	ll d = max(0ll, (a.F + a.S) - (b.F - b.S));
	return (4 * b.S * b.S - d * d);
}
 
pll get_val(int i, int j) {
	ll x1 = A[i + 1].F - A[i + 1].S, x2 = A[j].F + A[j].S;
	ll d = (x1 - x2) / 2; pll x = Mp(x1 + d, d);
	return Mp(dp[i].F + cal(A[i], x) + R, dp[i].S + 1);
}

void build(int v, int tl, int tr) {
	t[v] = 0;
	if (tr - tl == 1) return ;
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}

pll get_min(int v, int tl, int tr, int i) {
	pll res = get_val(t[v], i);
	if (tr - tl == 1) return res;
	int mid = (tl + tr) / 2;
	if (i < mid) res = min(res, get_min(2 * v + 1, tl, mid, i));
	else res = min(res, get_min(2 * v + 2, mid, tr, i));
	return res;
}

void upd_val(int v, int tl, int tr, int l, int r, int i) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	
	int mid = (tl + tr) / 2;
	if (l == tl && r == tr) {
		if (tr - tl == 1) {
			if (get_val(i, tl) < get_val(t[v], tl)) t[v] = i;
			return ;
		}
		
		pll x1 = get_val(i, tl), x2 = get_val(i, mid - 1);
		pll y1 = get_val(t[v], tl), y2 = get_val(t[v], mid - 1);
		if (x1 <= y1 && x2 <= y2) {
			int j = t[v]; t[v] = i;
			upd_val(2 * v + 2, mid, tr, l, r, j);
			return ;
		}
		else if (y1 <= x1 && y2 <= x2) {
			upd_val(2 * v + 2, mid, tr, l, r, i);
			return ;
		}
		
		x1 = get_val(i, mid), x2 = get_val(i, tr - 1);
		y1 = get_val(t[v], mid), y2 = get_val(t[v], tr - 1);
		if (x1 <= y1 && x2 <= y2) {
			int j = t[v]; t[v] = i;
			upd_val(2 * v + 1, tl, mid, l, r, j);
			return ;
		}
		else if (y1 <= x1 && y2 <= x2) {
			upd_val(2 * v + 1, tl, mid, l, r, i);
			return ;
		}
		
		return ;
	}
	upd_val(2 * v + 1, tl, mid, l, r, i); upd_val(2 * v + 2, mid, tr, l, r, i);
}

pll get_res(ll x) {
	dp[0] = Mp(0, 0);
	R = x; build(0, 0, n);
	for (int i = 1; i < n; i++) {
		dp[i] = get_min(0, 0, n, i);
		upd_val(0, 0, n, 0, n, i);
	}
	return dp[n - 1];
}

ll take_photos(int Nx, int Mx, int Kx, vector<int> rx, vector<int> cx) {
	n = Nx; m = Mx; k = Kx;
	for (int i = 0; i < n; i++) {
		if (cx[i] > rx[i]) swap(cx[i], rx[i]);
		a[i] = Mp(rx[i], cx[i]);
		ls[a[i].F].pb(i);
	}
	
	A.pb(Mp(0, 0));
	for (int i = m - 1; i >= 0; i--) {
		for (int j : ls[i]) {
			qu.push(Mp(-a[j].S, Mp(i, j)));
		}
		for (int j : ls[i]) {
			if (qu.top().S.S == j) {
				int x1 = a[j].F, y1 = a[j].S;
				A.pb(Mp(x1 + y1 + 1, x1 - y1 + 1));
			}
		}
	}
	sort(all(A));
	n = len(A); k = min(k, n - 1);
	
	ll l = -oo, r = oo;
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (get_res(mid).S <= k) r = mid;
		else l = mid;
	}
	
	pll R = get_res(r);
	ll ans = R.F - k * r;
	return ans / 4;
}

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