Submission #645437

#	Time	Username	Problem	Language	Result	Execution time	Memory
645437		ymm	Aliens (IOI16_aliens)	C++17	100 / 100	139 ms	9484 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100010;
pll a[N], dp[N];
int n;

vector<pair<pll,int>> con;

bool should_remove(pll a, pll b, pll c)
{
	return    (b.second - a.second) * (a.first - c.first)
	       <= (c.second - a.second) * (a.first - b.first);
}

void insert_con(pll p, int id)
{
	while (con.size() >= 2 && should_remove(p, (con.end()-1)->first,
	                                           (con.end()-2)->first))
		con.pop_back();
	con.push_back({p, id});
}

ll eval(pll p, ll x)
{
	return p.first * x + p.second;
}

ll area(ll i, ll j)
{
	return i > j? 0: (j-i)*(j-i);
}

pll calc(ll lambda)
{
	dp[0] = {0, 0};
	con.clear();
	insert_con({2*a[0].first, -a[0].first*a[0].first}, 0);
	int p = 0;
	Loop (i,0,n) {
		ll x = a[i].second;
		p = min(p, (int)con.size() - 1);
		while (p+1 < con.size() &&   eval(con[p  ].first, x)
		                           < eval(con[p+1].first, x))
			++p;
		int k = con[p].second;
		ll val =   area(a[k].first, a[i].second)
		         - (k? area(a[k].first, a[k-1].second): 0)
			 + lambda + dp[k].first;
		dp[i+1] = {val, dp[k].second+1};
		if (i+1 == n)
			return dp[n];
		insert_con({2*a[i+1].first, - a[i+1].first*a[i+1].first
		                          + area(a[i+1].first, a[i].second)
		                          - dp[i+1].first},
		           i+1);
	}
	return {-1, -1};
}

long long take_photos(int n, int m, int k, std::vector<int> r,
                                           std::vector<int> c)
{
	Loop (i,0,n) {
		a[i] = {r[i], c[i]};
		if (a[i].first > a[i].second)
			swap(a[i].first, a[i].second);
		a[i].second += 1;
	}
	sort(a, a+n, [](pll x, pll y){return x.first < y.first
	                                     || (x.first == y.first
	                                         && x.second > y.second);});
	for (int i = 0, j = 0; i < n; ++i) {
		if (!j || a[j-1].second < a[i].second) {
			a[j] = a[i];
			++::n;
			++j;
		}
	}
	ll bl = 0, br = (ll)m * m;
	while (bl < br) {
		ll mid = (bl + br)/2;
		int cnt = calc(mid).second;
		if (cnt > k)
			bl = mid+1;
		else
			br = mid;
	}
	return calc(bl).first - k*bl;
}

Compilation message (stderr)

aliens.cpp: In function 'pll calc(ll)':
aliens.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (p+1 < con.size() &&   eval(con[p  ].first, x)
      |          ~~~~^~~~~~~~~~~~

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