Submission #139190

#	Time	Username	Problem	Language	Result	Execution time	Memory
139190		nvmdava	Aliens (IOI16_aliens)	C++17	100 / 100	250 ms	14056 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

vector<pair<ll, ll> > tmp;
vector<ll> L(1, -1), R(1, -1);
int n;

struct Line{
	ll x, y, g;
	int id;
	Line(int _id, ll _x, ll _y, ll _g){
		x = _x;
		id = _id;
		y = _y;
		g = _g;
	}
	
	ll query(ll xx){
		return y - xx * g;
	}
	ll cross(ll _y, ll _g){
		ll dy = _y - y;
		ll dg = _g - g;
		return dy / dg + 1;
	}
};

vector<Line> line;
int cnt[100005];
ll ans[100005];
void calc(ll c){
	line.clear();
	int it = 0, sz = 0;
	line.push_back(Line(0, 0, L[1] * L[1], 2 * L[1]));
	for(int i = 1; i <= n; i++){
		while(it < sz && line[it + 1].x <= R[i]) it++;

		ans[i] = c + R[i] * R[i] + line[it].query(R[i]);
		cnt[i] = cnt[line[it].id] + 1;
		if(i == n) break;

		ll t = max(0LL, R[i] - L[i + 1]);
		ll yy = ans[i] - t * t + L[i + 1] * L[i + 1];
		ll gg = 2 * L[i + 1];

		while(sz >= 0 && line[sz].cross(yy, gg) <= line[sz].x){
			sz--;
			line.pop_back();
		}

		line.push_back(Line(i, 
			sz == -1 ? 0 : line[sz].cross(yy, gg),
			yy,
			gg));
		sz++;
		it = min(it, sz);

	}
}

ll take_photos(int n, int qq, int k, std::vector<int> rr, std::vector<int> cc) {
	for(int i = 0; i < n; i++){
		tmp.push_back({min(rr[i], cc[i]), - 1 - max(rr[i], cc[i])});
	}
	sort(tmp.begin(), tmp.end());
	int mxm = -1;
	for(auto& x : tmp){
		if(-x.second > mxm){
			mxm = -x.second;
			L.push_back(x.first);
			R.push_back(mxm);
		}
	}
	::n = n = L.size() - 1;

	ll l = 0, r = qq * 1LL * qq;
	while(l < r){
		ll m = (l + r) >> 1;
		calc(m);
		if(cnt[n] <= k) r = m;
		else l = m + 1;
	}
	calc(r);
	return ans[n] - k * r;
}

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