Submission #519579

#	Time	Username	Problem	Language	Result	Execution time	Memory
519579		AdamGS	Aliens (IOI16_aliens)	C++17	100 / 100	1232 ms	57100 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<long long,long long> pt;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7, MAXM=1e6+7;
const ll INF=1e18+7;
pt T[LIM];
pair<pt,int>tr[4*MAXM];
ll dp[LIM], lst[LIM], n, m, k, N=2;
ll f(pt a, ll x) {
	return a.st*x+a.nd;
}
void upd(pt x, int ind) {
	int v=1, l=0, r=N-1;
	while(true) {
		int mid=(l+r)/2;
		bool a=f(x, l)<f(tr[v].st, l);
		bool b=f(x, mid)<f(tr[v].st, mid);
		if(b) {
			swap(tr[v].st, x);
			swap(tr[v].nd, ind);
		}
		if(l==r) return;
		v*=2;
		if(a!=b) r=mid;
		else {
			++v;
			l=mid+1;
		}
	}
}
pair<ll,int>cnt(ll x) {
	int v=x+N;
	pair<ll,int>ans={INF, 0};
	while(v) {
		ans=min(ans, {f(tr[v].st, x), tr[v].nd});
		v/=2;
	}
	return ans;
}
int solve(ll c) {
	rep(i, 2*N) tr[i]={{0, INF}, MAXM};
	upd({-2*T[0].st, T[0].st*T[0].st-2*T[0].st}, -1);
	rep(i, n) {
		pair<ll,int>p=cnt(T[i].nd);
		dp[i]=p.st+T[i].nd*T[i].nd+2*T[i].nd+1+c;
		lst[i]=p.nd;
		if(i<n-1) {
			ll b=max(T[i].nd-T[i+1].st+1, 0ll);
			b*=-b;
			b+=dp[i]+T[i+1].st*T[i+1].st-2*T[i+1].st;
			upd({-2*T[i+1].st, b}, i);
		}
	}
	int akt=n-1, ans=0;
	while(akt>=0) {
		++ans;
		akt=lst[akt];
	}
	return ans;
}
ll take_photos(int Z, int M, int K, vector<int>r, vector<int>c) {
	pair<ll,ll>P[Z];
	rep(i, Z) P[i]={min(r[i], c[i]), -max(r[i], c[i])};
	sort(P, P+Z);
	ll ma=-1;
	rep(i, Z) {
		if(-P[i].nd>ma) {
			ma=-P[i].nd;
			T[n]={P[i].st, -P[i].nd};
			++n;
		}
	}
	m=M; k=K;
	while(N<m) N*=2;
	ll po=0, ko=10000000000000;
	while(po<ko) {
		ll sr=(po+ko)/2;
		if(solve(sr)>k) po=sr+1; else ko=sr;
	}
	solve(po);
	return dp[n-1]-po*k;
}

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