Submission #540906

#	Time	Username	Problem	Language	Result	Execution time	Memory
540906		keta_tsimakuridze	Aliens (IOI16_aliens)	C++14	100 / 100	1956 ms	124828 KiB

aliens

#include "aliens.h"

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
using namespace std;
const ll N = 1e6 + 5;
ll n, m, cntL[N], cntR[N], R[N];
pii dp[N];
vector<ll> st[N], new_[N];
struct line{
	ll k, b, cn;
};
double _(line a, line b) {
	// a.k * x + a.b = b.k * x + 
	return (double)(a.b - b.b) / (b.k - a.k);
}
ll f(line c, ll x) {
	return ((ll)c.k * x + c.b);
}
ll check(ll c) {
	deque<line> dq;
	ll mx = 0;
	for(ll x = 1; x <= n; x++) {
		dp[x] = {n * n + 5, 0};
		if(cntL[x - 1] + cntR[x + 1] == m) dp[x] = dp[x - 1];
		for(ll j = 0; j < new_[x].size(); j++) {
			ll l = new_[x][j];
			line a;
			ll r = R[l - 1];
			a.b = dp[r].f - (ll)(r - l + 1) * (r - l + 1) + (ll)l * l + 1 - 2 * l;
			a.k = -l; mx = max(mx, l);
			assert(mx == l);
			a.cn = -dp[r].s;
			
			while(dq.size() >= 2) {
				line cur = dq.back();
				line prev = dq[(ll)dq.size() - 2];
				if(_(cur, prev) >= _(prev, a)) dq.pop_back();
				else if(_(cur, prev) == _(prev, a) && cur.cn <= a.cn) dq.pop_back();
				else break;
			} 
			
			dq.push_back(a);
		}
		
		while(dq.size() >= 2) {
			line cur = dq[0];
			line nxt = dq[1];
			if(f(nxt, 2 * x) < f(cur, 2 * x)) dq.pop_front();
			else if(f(nxt, 2 * x) == f(cur, 2 * x) && nxt.cn >= cur.cn) dq.pop_front();
			else break;
		}
		
		
		if(dq.size()) {
			ll y = f(dq[0], 2 * x)  + (ll)x * x + 2 * x  + c;
			dp[x] = min(dp[x], {y, -(dq[0].cn + 1)});
		}
	}
	
	return -dp[n].s;
}
long long take_photos(int N, int M, int k, std::vector<int> r1, std::vector<int> c) {
	swap(N, M); 
	m = M; n = N;
//	vector<ll> l(m + 5);
	ll mnl = n, mxr = 0;
    for(ll i = 0; i < m; i++) {
    	if(c[i] > r1[i]) swap(c[i], r1[i]);
    	ll l = min(r1[i], c[i]); r1[i] = max(r1[i], c[i]);
    	l++; r1[i]++;
    	cntL[r1[i]]++; cntR[l]++;
    	st[l].push_back(r1[i]);
    	mnl = min(l, (ll)mnl); mxr = max(mxr, (ll)r1[i]);
	}
	if(k == 1) {
		return (ll)(mxr - mnl + 1) * (mxr - mnl + 1);
	}
	for(ll i = 1; i <= n; i++) cntL[i] += cntL[i - 1];
	for(ll i = n; i >= 1; i--) cntR[i] += cntR[i + 1];
	ll C = 0;
	for(ll i = 1; i <= n; i++) {
		C = max(C, i);
		for(ll j = 0;j < st[i].size(); j++) {
			C = max(C, st[i][j]);
		}
		R[i] = C;
		new_[R[i - 1] + 1].push_back(i);
	}
	ll l = 0, r = 1e13, p = 0;
	while(l <= r) {
		ll mid = (l + r) / 2;
		if(check(mid) >= k) {
			p = mid;
			l = mid + 1;
			
		} else r = mid - 1;
	}
	check(p); 
	return dp[n].f - (ll)p * k;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int check(long long int)':
aliens.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(ll j = 0; j < new_[x].size(); j++) {
      |                 ~~^~~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:87:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(ll j = 0;j < st[i].size(); j++) {
      |                ~~^~~~~~~~~~~~~~

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