Submission #521910

#	Time	Username	Problem	Language	Result	Execution time	Memory
521910		jjang36524	Aliens (IOI16_aliens)	C++14	100 / 100	131 ms	12048 KiB

aliens

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#define int long long
using namespace std;
int x[1000100];
int y[1000100];
int dp[1000100];
int cnt[1010100];
vector<pair<pair<int, int>, pair<int, int>>>s;
int N;
pair<int, int> getv(int c)
{
	s.clear();
	int nowpos = 0;
	int i;
	for (i = 0; i < N; i++)
	{
		int sp = -2 * x[i];
		int yp = (i ? dp[i - 1] : 0) + x[i] * x[i] - (i ? (max(0LL, y[i - 1] - x[i] + 1) * (max(0LL, y[i - 1] - x[i] + 1))) : 0);
		int p = 0;
		while (s.size())
		{
			p = (yp - s.back().first.second) / (s.back().first.first - sp);
			if (s.back().second.first < p)
				break;
			if (nowpos == s.size())
				nowpos--;
			s.pop_back();
		}
		s.push_back({ {-2 * x[i],(i ? dp[i - 1] : 0) + x[i] * x[i] - (i ? (max(0LL,y[i - 1] - x[i] + 1) * (max(0LL,y[i - 1] - x[i] + 1))) : 0)},{p,(i?cnt[i - 1]:0)} });
		while (nowpos < s.size() - 1 && s[nowpos + 1].second.first < y[i] + 1)
			nowpos++;
		dp[i] = s[nowpos].first.first * (y[i] + 1) + s[nowpos].first.second + (y[i] + 1) * (y[i] + 1) + c;
		cnt[i] = s[nowpos].second.second + 1;
	}
	return { cnt[N - 1],dp[N - 1] };
}
long long take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c)
{
	vector<pair<int, int>>so;
	int i;
	for (i = 0; i < n; i++)
	{
		so.push_back({ min(r[i],c[i]),max(r[i],c[i]) });
	}
	sort(so.begin(), so.end());
	int si = 0;
	for (i = 0; i < n; i++)
	{
		if (si>0&&x[si - 1] == so[i].first)
		{
			x[si - 1] = so[i].first;
			y[si - 1] = so[i].second;
		}
		else if (si == 0 || y[si - 1] < so[i].second)
		{
			x[si] = so[i].first;
			y[si] = so[i].second;
			si++;
		}
		
	}
	N = si;
	k = min(k, (signed)N);
	int s = 0, e = 1LL << 40;
	pair<int, int>rv = { 1LL << 40,0 };
	pair<int, int>lv = { 0,0 };
	while (s <= e)
	{
		int m = (s + e) / 2;
		auto v = getv(m);
		if (v.first == k)
		{
			return v.second - k * m;
		}
		else if (v.first < k)
		{
			e = m - 1;
			lv = max(lv, make_pair(v.first, v.second - v.first * m));
		}
		else
		{
			s = m + 1;
			rv = min(rv, make_pair(v.first, v.second - v.first * m));
		}
	}
	return rv.second + (lv.second - rv.second) / (rv.first - lv.first) * (rv.first - k);
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, long long int> getv(long long int)':
aliens.cpp:28:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    if (nowpos == s.size())
      |        ~~~~~~~^~~~~~~~~~~
aliens.cpp:33:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   while (nowpos < s.size() - 1 && s[nowpos + 1].second.first < y[i] + 1)
      |          ~~~~~~~^~~~~~~~~~~~~~

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