Submission #172823

#	Time	Username	Problem	Language	Result	Execution time	Memory
172823		figter001	Aliens (IOI16_aliens)	C++17	25 / 100	15 ms	636 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int n,k;
vector<pair<int,int>> segments;
vector<ll> rem;
int cnt;

struct con{
	int l,used;
	ll prev;
	con(int left,int uu,ll pp){
		l = left;used = uu;prev = pp;
	}

	pair<ld,int> getcost(ld x){
		ld d = l-x;
		return {d*d + prev ,used};
	}

	ld tover(con rhs){
		ld l1 = l,l2 = rhs.l;
		ld c = prev - rhs.prev;
		ld all = l1*l1 - l2 * l2 + c;
		ld rem = 2 * l1 - 2 * l2;
		all /= rem;
		return all;
	}
};

pair<ll,ll> calc(ll cst){

	pair<ll,int> curbest = {0,0};
	int fptr=0,bptr=0;
	vector<con> bag(cnt+2,con(0,0,0));

	for(int i=0;i<cnt;i++){
		int l = segments[i].first;
		int r = segments[i].second;
		con nxt = con(l-1,curbest.second+1,curbest.first + cst-rem[i]);
		while(bptr - fptr >= 2 && bag[bptr-2].tover(bag[bptr-1]) >= bag[bptr-2].tover(nxt))bptr--;
		bag[bptr++] = nxt;
		while(fptr + 1 < bptr && bag[fptr].getcost(r) >= bag[fptr+1].getcost(r))fptr++;
		curbest = bag[fptr].getcost(r);
	}
	return curbest;
}

ll find_answer(){
	ll md,lo=0,hi=2e10,lamda = -1;
	pair<ll,ll> tst = calc(0);
	if(tst.second <= k)return tst.first;
	while(lo <= hi){
		md = (lo + hi)/2;
		ll used = calc(md).second;
		if(used <= k){
			hi = md-1;
			lamda = md;
		}else{
			lo = md+1;
		}
	}
	pair<ll,ll> ans = calc(lamda);
	return ans.first - lamda * k;
}

ll take_photos(int N,int m,int K,vector<int> R, vector<int> C){
	n = N;k = K;
	vector<pair<int,int>> tmp;
	for(int i=0;i<n;i++){
		int r = R[i];
		int c = C[i];
		tmp.push_back({max(r,c) , min(r,c)});
	}
	sort(tmp.begin(),tmp.end());
	set<pair<int,int>> st;
	for(int i=0;i<n;i++){
		int l = tmp[i].second;
		int r = tmp[i].first;
		while(st.size() && -st.begin()->first >= l){
			st.erase(st.begin());
		}
		st.insert({-l,r});
	}
	while(st.size()){
		pair<int,int> it = *st.begin();
		st.erase(st.begin());
		it.first = -it.first;
		// cout << it.first << ' ' << it.second << endl;
		segments.push_back(it);
	}
	reverse(segments.begin(),segments.end());
	cnt = segments.size();
	rem.resize(cnt);

	for(int i=1;i<cnt;i++){
		int fr = segments[i].first;
		int bf = segments[i-1].second;
		if(bf >= fr){
			rem[i] = bf - fr + 1;
			rem[i] *= rem[i];
		}
	}

	ll ans = find_answer();
	return ans;
}

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