Submission #1036453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036453		AmirAli_H1	Aliens (IOI16_aliens)	C++17	100 / 100	1758 ms	58960 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 = 1e5 + 4;
const int maxs = 2e6 + 4;
const ll oo = 1e12 + 4;

int n, m, k;
pii a[maxn]; pll dp[maxn];
vector<int> ls[maxs]; vector<pii> A;
priority_queue<pair<int, pii>> qu;
ll R; int t[4 * maxn];

ll cal(pll a, pll b) {
	ll d = max(0ll, (a.F + a.S) - (b.F - b.S)) / 2;
	return (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);
}

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

void upd_val(int v, int tl, int tr, int i) {
	while (true) {
		int mid = (tl + tr) / 2;
		if (get_val(i, mid) < get_val(t[v], mid)) swap(t[v], i);
		if (tr - tl == 1) break;
		
		if (get_val(i, tl) < get_val(t[v], tl)) {
			v = 2 * v + 1; tr = mid;
		}
		else {
			v = 2 * v + 2; tl = mid;
		}
	}
}

pll get_res(ll x) {
	dp[0] = Mp(0, 0);
	R = x; fill(t, t + (4 * n), 0);
	for (int i = 1; i < n; i++) {
		dp[i] = get_min(0, 0, n, i);
		upd_val(0, 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 = -1, 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;
}

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