Submission #955575

#	Time	Username	Problem	Language	Result	Execution time	Memory
955575		CaiWinDao	Aliens (IOI16_aliens)	C++17	100 / 100	396 ms	13232 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 100005;

vector<pi> v;
pi dp[MAXN];

struct point{
	lint first;
	lint second;
	int cnt;
};

struct cht{
	vector<point> v;
	void clear(){ v.clear(); }
	long double cross(point a, point b){
		return ((long double)(b.second - a.second) / (b.first - a.first));
	}
	void add_line(int x, lint y, int z){
		while(v.size() >= 2 && cross(v[v.size()-2], v.back()) > cross(v.back(), (point){x, y, z})){
			v.pop_back();
		}
		v.push_back({x, y, z});
	}
	pi query(int x){
		int s = 0, e = v.size()-1;
		auto f = [&](int p){
		return v[p].first * x + v[p].second;
		};
		while(s != e){
			int m = (s+e)/2;
			if(f(m) <= f(m+1)) e = m;
			else s = m+1;
		}
		return pi(v[s].first * x + v[s].second, v[s].cnt);
	}
}cht;

pi trial(lint l){
	cht.clear();
	for(int i=1; i<=v.size(); i++){
		cht.add_line(2 * 2 * v[i-1].first, dp[i-1].first + 2ll * v[i-1].first * v[i-1].first, dp[i-1].second);
		dp[i] = cht.query(-v[i-1].second);
		dp[i].first += 2ll * v[i-1].second * v[i-1].second + l;
		dp[i].second++;
		if(i != v.size()){
			lint c = max(0ll, v[i-1].second - v[i].first);
			dp[i].first -= 2 * c * c;
		}
	}
	return dp[v.size()];
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	vector<pi> w;
	for(int i=0; i<n; i++){
		if(r[i] > c[i]) swap(r[i], c[i]);
		w.push_back({r[i]-1, c[i]});
	}
	sort(w.begin(), w.end(), [&](const pi &a, const pi &b){
		return pi(a.first, -a.second) < pi(b.first, -b.second);
	});
	for(auto &i : w){
		if(v.empty() || v.back().second < i.second){
			v.push_back(i);
		}
	}
	lint s = 0, e = 2e12;
	while(s != e){
		lint m = (s+e)/2;
		if(trial(2 * m + 1).second <= k) e = m;
		else s = m+1;
	}
	return trial(s * 2).first / 2 - s * k;
}

Compilation message (stderr)

aliens.cpp: In function 'pi trial(lint)':
aliens.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=1; i<=v.size(); i++){
      |               ~^~~~~~~~~~
aliens.cpp:50:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   if(i != v.size()){
      |      ~~^~~~~~~~~~~

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