Submission #1084896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084896		fyan	Aliens (IOI16_aliens)	C++14	100 / 100	167 ms	8148 KiB

aliens

#include "bits/stdc++.h"
using namespace std;
#define int int64_t 
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int MXN=1e5+5, INF=1e9;
int N,M,K;
array<int,2> arr[MXN];
int dp[MXN], amt[MXN];

bool cc1(const array<int,2> &a, const array<int,2> &b) {
	if (a[0]==b[0]) {
		return a[1]>b[1];
	}
	return a[0]<b[0];
}
bool cc2(const array<int,2> &a, const array<int,2> &b) {
	return a[1]<b[1];
}

namespace monoline {
	const int lo = -10, hi = 1e6+5;
	deque<array<int,5>> lines;
	
	void reset() {while (sz(lines)) lines.pop_back();}
	int eval(array<int,5> a, int x) {
		return a[0]*x+a[1];
	}
	int first_lower(array<int,5> a, array<int,5> b) {
		if (eval(a,lo)<=eval(b,lo) && eval(a,hi)<=eval(b,hi)) {return -69420;}
		if (eval(a,lo)>=eval(b,lo) && eval(a,hi)>=eval(b,hi)) {return 0;}
		int fp = (a[1]-b[1])/(b[0]-a[0]);
		fp--;
		while (eval(a,fp) <= eval(b,fp)) {
			fp++;
		}
		return fp;
	}
	void insert_line(int m, int b, int v=0) {
		array<int,5> ln = {m,b,v,-69,-69};
		while (1) {
			if (!sz(lines)) {
				ln[3] = lo, ln[4] = hi;
				lines.push_back(ln);
				return;
			}
			array<int,5>& pv = lines.back();
			pv[4] = hi;
			int fp = first_lower(pv,ln);
			if (fp==-69420) return;
			if (fp <= pv[3]) {
				lines.pop_back();
				continue;
			}
			pv[4] = fp-1;
			ln[3] = fp, ln[4] = hi;
			lines.push_back(ln);
			return;
		}
	}
	array<int,2> get_value(int x) {
		while (lines.front()[4] < x) {
			lines.pop_front();
		}
		int vv = eval(lines.front(),x);
		if (sz(lines)>1) {
			auto temp = lines.front(); lines.pop_front();
			if (eval(lines.front(),x) >= vv) {
				lines.push_front(temp);
			}
		}
		return {eval(lines.front(),x),lines.front()[2]};
	}
}

int check(int w) {
	memset(dp,0x3f,sizeof(dp));
	memset(amt,0,sizeof(amt));
	dp[0] = 0;
	monoline::reset();
	monoline::insert_line(-2*(arr[0+1][0]-1), dp[0] + (arr[0+1][0]-1)*(arr[0+1][0]-1) - (max(0ll,arr[0][1]-arr[0+1][0]+1ll))*(max(0ll,arr[0][1]-arr[0+1][0]+1ll)),0);
	for (int i=1; i<=N; i++) {
		auto [v,a] = monoline::get_value(arr[i][1]); 
		dp[i] = v+w+arr[i][1]*arr[i][1]; 
		amt[i] = a+1;
		monoline::insert_line(-2*(arr[i+1][0]-1), dp[i] + (arr[i+1][0]-1)*(arr[i+1][0]-1) - (max(0ll,arr[i][1]-arr[i+1][0]+1ll))*(max(0ll,arr[i][1]-arr[i+1][0]+1ll)),amt[i]);
	}
	return amt[N];
}

int search(int lo, int hi) {
	if (lo==hi) return lo;
	if (lo+1==hi) {
		if (check(hi)==K) return hi;
		return lo;
	}
	int mid = (lo+hi)/2;
	if (check(mid) <= K) {
		return search(lo,mid);
	}
	return search(mid,hi);
}

int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
	N = n, M = m, K = k;
	for (int i=1; i<=N; i++) {
		arr[i] = {min(r[i-1],c[i-1]),max(r[i-1],c[i-1])};
	}
	arr[0] = {-INF,-INF};
	sort(arr,arr+N+1,cc1);
	int pv = 0,sub = 0;
	for (int i=1; i<=N; i++) {
		if (arr[pv][1] >= arr[i][1]) {
			sub++; arr[i] = {INF,INF};
		} else pv = i;
	}
	sort(arr,arr+1+N,cc2);
	N -= sub; K = min(K,N);
	
	int w = search(-1e12,1e12);
	check(w);
	while (amt[N] > K) {
		w++; check(w);
	}
	return dp[N]-w*(K);
}

/*
signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	int32_t a,b,c; cin>>a>>b>>c;
	vector<int32_t> x(a),y(a);
	for (int i=0; i<a; i++) {
		cin>>x[i]>>y[i];
	}
	cout<<take_photos(a,b,c,x,y);
	
	return 0;
}
*/

Compilation message (stderr)

aliens.cpp: In function 'int64_t check(int64_t)':
aliens.cpp:84:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |   auto [v,a] = monoline::get_value(arr[i][1]);
      |        ^

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