Submission #377223

#	Time	Username	Problem	Language	Result	Execution time	Memory
377223		Jasiekstrz	Aliens (IOI16_aliens)	C++17	100 / 100	187 ms	8556 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
#define fi first
#define se second
using namespace std;

const long long INF=(long long)1e18+7;
const int N=1e5;

struct Interval
{
	long long l,r;

	Interval(int row=-1,int col=-1)
	{
		l=row;
		r=col;
		if(l>r)
			swap(l,r);
		return;
	}
	inline bool operator<(const Interval &oth) const
	{
		if(l==oth.l)
			return r>oth.r;
		return l<oth.l;
	}
	inline long long common(Interval oth)
	{
		if(oth.r<l || r<oth.l)
			return 0;
		if(oth.r>r)
			return r-oth.l+1;
		return oth.r-l+1;
	}
	inline long long size()
	{
		return r-l+1;
	}
};

struct Ans
{
	long long w,k;

	Ans(long long _w=0,long long _k=0) : w(_w),k(_k) {}
};

struct Function
{
	long long a,b;
	int id;

	Function(long long _a,long long _b,int _id) : a(_a),b(_b),id(_id) {}
	inline long long f(long long x)
	{
		return x*x+a*x+b;
	}
	inline long long better(Function &oth)
	{
		if(oth.a==a)
			return INF;
		return (oth.b-b+a-oth.a)/(a-oth.a);
	}
};

Interval tab[N+10];
long long dp[N+10];
int kk[N+10];
long long cross[N+10];
long long sub[N+10];
deque<Function> dq;

inline bool try_pop(int i)
{
	if(dq.size()<2)
		return false;
	Function t=dq.front();
	dq.pop_front();
	if(dq.front().f(tab[i].r)<t.f(tab[i].r))
		return true;
	dq.push_front(t);
	return false;
}

inline bool try_pop_back(Function &x)
{
	if(dq.size()<2)
		return false;
	if(x.f(cross[dq.back().id])<dq.back().f(cross[dq.back().id]))
	{
		dq.pop_back();
		return true;
	}
	return false;
}

inline void try_push(int i,long long c)
{
	Function t(-2*(tab[i+1].l-1),dp[i]+c-sub[i+1]+(tab[i+1].l-1)*(tab[i+1].l-1),i);
	while(try_pop_back(t));
	if(!dq.empty())
		cross[i]=t.better(dq.back());
	dq.push_back(t);
	return;
}

inline Ans solve(int n,long long c)
{
	int i;
	dq.clear();
	dp[0]=0;
	kk[0]=0;
	try_push(0,c);
	for(i=1;i<=n;i++)
	{
		while(try_pop(i));
		kk[i]=kk[dq.front().id]+1;
		dp[i]=dq.front().f(tab[i].r);
		try_push(i,c);
	}
	return Ans(dp[n],kk[n]);
}

long long take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
	int i,j;
	long long ans=0;
	for(i=1;i<=n;i++)
	{
		tab[i]=Interval(r[i-1],c[i-1]);
	}
	sort(tab+1,tab+n+1);
	for(i=1,j=-1;i<=n;i++)
	{
		if(tab[i].r<=j)
			tab[i].l=m+1;
		j=max(j,(int)tab[i].r);
	}
	sort(tab+1,tab+n+1);
	for(i=1;i<=n && tab[i].l<m;i++);
	n=i-1;
	tab[0]=Interval(-1,-1);
	tab[n+1]=Interval(m+1,m+1);
	if(n<=k)
	{
		for(i=1;i<=n;i++)
			ans+=tab[i].size()*tab[i].size()-tab[i].common(tab[i-1])*tab[i].common(tab[i-1]);
		return ans;
	}
	for(i=1;i<=n;i++)
	{
		sub[i]=tab[i].common(tab[i-1]);
		sub[i]*=sub[i];
	}
	long long bg=0,en=(long long)m*m,mid;
	while(bg<en)
	{
		mid=(bg+en)/2;
		Ans tmp=solve(n,mid);
		if(tmp.k<=k)
			en=mid;
		else
			bg=mid+1;
	}
	Ans tmp=solve(n,bg);
    return tmp.w-bg*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