Submission #139024

#	Time	Username	Problem	Language	Result	Execution time	Memory
139024		nvmdava	Aliens (IOI16_aliens)	C++17	4 / 100	3 ms	380 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second

struct Line{
	int id;
	ll x, y, g;
	Line(int _id, int _x, int _y, int _g){
		id = _id;
		x = _x;
		y = _y;
		g = _g;
	}

	ll cross(ll y_, ll g_){
		ll dy = y - y_;
		ll dg = g - g_;
		return dy / dg + (dy % dg != 0);
	}

	ll query(ll xx){
		return y - g * xx;
	}
};

int cnt[100005];
ll ans[100005];
vector<Line> line;
int n;
vector<pair<int, int> > tmp, a;
bool ooo = 0;
void calc(ll c){
	line.clear();
	int it = 0, sz = 0;
	line.push_back(Line(0, 0, a[1].ff * a[1].ff, 2 * a[1].ff));
	
	for(int i = 1; i <= n; i++){
		while(it < sz && line[it + 1].x <= a[i].ss)
			it++;
		
		ans[i] = line[it].query(a[i].ss) + c + a[i].ss * a[i].ss;
		cnt[i] = cnt[line[it].id] + 1;
		
		if(i == n) break;
		
		ll xx = max(0, a[i].ss - a[i + 1].ff);
		ll yy = ans[i] + a[i + 1].ff * a[i + 1].ff - xx * xx;
		ll gg = 2 * a[i + 1].ff;
		
		while(sz >= 0 && line[sz].cross(yy, gg) <= line[sz].x){
			line.pop_back();
			sz--;
		}
		
		sz++;
		
		line.push_back(Line(i,
			sz == 0 ? 0 : line[sz - 1].cross(yy, gg), 
			yy, 
			gg));
		it = min(it, sz);
	}
} 


ll take_photos(int n, int qq, int k, std::vector<int> rr, std::vector<int> c) {
	
	for(int i = 0; i < n; i++)
		tmp.push_back({min(rr[i], c[i]), -max(c[i], rr[i])});
	int mxm = -1;
	sort(tmp.begin(), tmp.end());
	a.push_back({-1, -1});
	if(ooo)cout<<'\n';
	for(auto& x : tmp){
		if(mxm < -x.ss){
			a.push_back({x.ff, 1 - x.ss});
			mxm = -x.ss;
			if(ooo)cout<<x.ff<<' '<<1 - x.ss<<'\n';
		}
	}
	if(ooo) cout<<'\n';
	
	::n = n = a.size() - 1;
	ll l = 0, r = 1000000000;

	while(l < r){
		double m = (l + r) / 2;
		calc(m);
		if(cnt[n] <= k) r = m;
		else l = m + 1;
	}
	calc(r);

	return ans[n] - cnt[n] * r; 
}

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