Submission #209561

#	Time	Username	Problem	Language	Result	Execution time	Memory
209561		oolimry	Aliens (IOI16_aliens)	C++14	100 / 100	236 ms	8036 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> ii;
vector<ii> allRanges; ///all the ranges
vector<ii> arr; ///non-overalping ranges we need to consider

inline long long square(long long x){ return x * x; }

bool comp(ii a, ii b){
	if(a.first == b.first) return a.second > b.second;
	return a.first < b.first;
}

struct Line{ long long m, c, taken; };

inline long double intersect(Line a, Line b){
	return (long double) (b.c - a.c) / (long double) (a.m - b.m);
}

struct ConvexHull{
	Line hull[100005];
	int l = 0, r = -1;
	
	void reset(){
		l = 0, r = -1;
	}
	
	///take as many if tie by cost
	bool redundantBack(){
		if(r - l < 2) return false;
		if(abs(intersect(hull[r],hull[r-1]) - intersect(hull[r-2],hull[r])) <= 0.00000001) return hull[r].taken > hull[r-1].taken; 
		return intersect(hull[r-1],hull[r-2]) > intersect(hull[r],hull[r-2]);
	}
	
	///return the best value, and also how many ranges taken
	ii getBest(long long k){		
		while(r - l > 0 && intersect(hull[l],hull[l+1]) < (long double) k) l++;
		long long ans = (hull[l].m * k + hull[l].c);
		return ii(ans, hull[l].taken);
	}
	
	void addLine(long long m, long long c, long long taken){		
		if(r - l < 0 || hull[r].m > m) hull[++r] = {m,c,taken};
		else if(hull[r].c > c) hull[r] = {m,c,taken};
		else if(hull[r].c == c && hull[r].taken < taken) hull[r] = {m,c,taken}; ///tiebreak by no. taken
		
		while(redundantBack()){
			hull[r-1] = hull[r];
			r--;
		}
	}
	
	
} ch;


///This is the dp part. There is no restriction on the number of ranges.
///However, the dp value increases by cost for every range taken.
///This returns the optimum value and the max no. of ranges taken for that value of cost
inline ii monge(long long cost){
	ch.reset();
	ch.addLine(-2LL * arr[0].first, square(arr[0].first), 1); ///option for taking from the start
	
	ii dp; ///ii(bestAns, taken)
	for(int i = 0;i < (int) arr.size();i++){
		ii x = arr[i];
		dp = ch.getBest(x.second);
		dp.first += square(x.second);
		dp.first += cost; ///add a cost for taking a range
		
		if(i != (int) arr.size() - 1){
			long long gradient = -2 * arr[i+1].first;
			long long yIntercept = dp.first - square(max(0LL, arr[i].second - arr[i+1].first)) + square(arr[i+1].first);
			
			ch.addLine(gradient, yIntercept, dp.second + 1);
		}
	}
	
	return dp;
}

long long take_photos(int n, int m, int K, vector<int> L, vector<int> R) {

	for(int i = 0;i < n;i++){
		if(L[i] > R[i]) swap(L[i], R[i]);
		allRanges.push_back(ii(L[i],R[i]));
	}
	
	///sort the ranges
	sort(allRanges.begin(),allRanges.end(),comp);
	
	///remove all ranges which are fully contained in another
	int maxR = -1;
	for(ii r : allRanges){
		if(r.second > maxR){
			maxR = r.second;
			arr.push_back(ii(r.first,r.second+1));
		} 
	}
	
	if(arr.size() == 1){
		return square(arr[0].second - arr[0].first);
	}
		
	long long low = -1;
	long long high = square(m);
	
	///Let f(k) be the answer to the problem where k is the no. of ranges we take
	///f is concave upwards [f(i) - f(i+1) <= f(i-1) - f(i)], diminishing returns
	///Hence, if we let g(k) = f(k) + k * cost, then g(k) has a local minimum where gradient of f(k) = C
	///As C increases, the local minimum point decreases (greater cost -> take fewer ranges)
	///We can binary search the value of C such that the local minimum point occurs at K given in the qn
	while(true){
		if(low == high - 1) break;
		long long s = (low + high) / 2LL;
		
		if(monge(s).second <= K) high = s;
		else low = s;
	}
	
	///We need to do linear interpolation since the function is not strictly concave up
	ii ansHigh = monge(high);
	long long ans = ansHigh.first - K * high;
	
    return ans;
}

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