Submission #406015

#	Time	Username	Problem	Language	Result	Execution time	Memory
406015		cgiosy	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	204 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct lr {
	int l, r;
	bool operator<(lr b) const { return l<b.l; }
};
struct point {
	ll x, y;
	ll operator()(ll z) const { return x*z+y; }
};
ll ccw(point& o, point& a, point& b) {
	return (o.x-a.x)*(o.y-b.y)-(o.y-a.y)*(o.x-b.x);
}
ll pw(int x) { return ll(x)*x; }

ll take_photos(int N, int M, int K, vector<int> L, vector<int> R) {
	lr A[N+1];
	for(int i=0; i<N; i++) {
		int x=L[i], y=R[i];
		A[i]={min(x, y)-1, max(x, y)};
	}
	sort(A, A+N);
	int N2=0;
	for(int i=1; i<N; i++) if(A[N2].r<A[i].r)
		A[N2+=A[N2].l<A[i].l]=A[i];
	K=min(K, N=N2+1);

	point H[N+1];
	int D[N+1];
	A[N].l=A[N-1].r;
	auto f=[&](ll m, int k=INT_MAX) {
		int s=0, e=0;
		H[0]={A[0].r, 0};
		for(int i=0; i<N; i++) {
			auto[l,r]=A[i];
			while(s<e && H[s](r)>H[s+1](r)) s++;
			point p{-l, H[s](r) + pw(l)+pw(r)-pw(max(r-A[i+1].l, 0)) - m};
			while(s<e && ccw(H[e-1], H[e], p)>=0) e--;
			H[++e]=p;
			D[e]=D[s]+1;
			if(D[e]>k) return ll(-1);
		}
		return H[e].y-pw(A[N-1].l)-pw(A[N-1].r);
	};
	ll l=-pw(M), r=0;
	while(l<r) {
		ll m=l+r+1>>1;
		if(~f(m, K)) l=m;
		else r=m-1;
	}
	return f(r)+K*r;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:49:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   ll m=l+r+1>>1;
      |        ~~~^~

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