Submission #377047

#	Time	Username	Problem	Language	Result	Execution time	Memory
377047		Jasiekstrz	Aliens (IOI16_aliens)	C++17	0 / 100	2 ms	1948 KiB

aliens

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

const long long INF=1e18L+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 oth.r-l+1;
		return r-oth.l+1;
	}
	inline long long size()
	{
		return r-l+1;
	}
};

Interval tab[N+10];
bool on[N+10];
pair<int,int> u[N+10];
set<pair<long long,int>> pq;

inline long long merge_cost(long long l1,long long r1,long long l2,long long r2)
{
	long long c=r2-l1,a=r1-l1,b=r2-l2,d=Interval(l1,r1).common(Interval(l2,r2));
	return c*c-a*a-b*b+d*d;
}
inline long long merge_cost(Interval a,Interval b)
{
	return merge_cost(a.l,a.r,b.l,b.r);
}

inline long long cost(int x,int n)
{
	if(!on[x])
		return merge_cost(tab[u[x-1].fi].l,tab[x-1].r,tab[x].l,tab[u[x+1].se].r);
	if(on[x] && (x-1>1 && !on[x-1]) && (x+1<=n && !on[x+1]))
	{
		return -merge_cost(tab[x-1],tab[x])
			+merge_cost(tab[u[x-2].fi].l,tab[x-2].r,tab[x-1].l,tab[x-1].r)
			+merge_cost(tab[x].l,tab[x].r,tab[x+1].l,tab[u[x+1].se].r);
	}
	return INF;
}

inline void try_insert(int x,int n)
{
	if(x<=1 || n<x)
		return;
	long long c=cost(x,n);
	if(c>=INF)
		return;
	if(pq.find({c,x})!=pq.end())
		pq.erase({c,x});
	else
		pq.insert({c,x});
	return;
}

inline void upd(int x,int n)
{
	if(!on[x])
	{
		on[x]=true;
		u[x].fi=x-1;
		u[x-1].se=x;
		return;
	}
	on[x]=false;
	on[x-1]=on[x+1]=true;

	u[u[x-2].fi].se=x-1;
	u[x-1]=u[u[x-2].fi];

	u[u[x+1].se].fi=x;
	u[x]=u[u[x+1].se];
	return;
}

long long take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
	int ki,i,j;
	long long ans=0;
	for(i=1;i<=n;i++)
	{
		tab[i]=Interval(r[i-1],c[i-1]);
		on[i]=false;
		u[i]={i,i};
	}
	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);
	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]);
		if(i>1)
			pq.insert({cost(i,n),i});
	}
	for(ki=n;ki>k;ki--)
	{
		int x=(pq.begin()->se);
		pq.erase(pq.begin());
		ans+=cost(x,n);
		try_insert(x-1,n);
		try_insert(x+1,n);
		upd(x,n);
		for(int it:{x-1,x,x+1})
			try_insert(it,n);
	}
    return ans;
}

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