제출 #377177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377177		Jasiekstrz	Aliens (IOI16_aliens)	C++17	4 / 100	11 ms	2028 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;
	}
};

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+1,a=r1-l1+1,b=r2-l2+1,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].se].r);
	if(on[x] && u[x-1].fi>1 && u[x].se+1<=n)
	{
		return -merge_cost(tab[u[x-1].fi].l,tab[x-1].r,tab[x].l,tab[u[x].se].r)
			+merge_cost(tab[u[u[x-1].fi-1].fi].l,tab[u[x-1].fi-1].r,tab[u[x-1].fi].l,tab[x-1].r)
			+merge_cost(tab[x].l,tab[u[x].se].r,tab[u[x].se+1].l,tab[u[u[x].se+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;
		pair<int,int> tmp={u[x-1].fi,u[x].se};
		for(int i=tmp.fi;i<=tmp.se;i++)
			u[i]=tmp;
		return;
	}
	on[x]=false;
	on[u[x-1].fi]=on[u[x].se+1]=true;

	pair<int,int> tmp={u[u[x-1].fi-1].fi,x-1};
	for(int i=tmp.fi;i<=tmp.se;i++)
		u[i]=tmp;

	tmp={x,u[u[x].se+1].se};
	for(int i=tmp.fi;i<=tmp.se;i++)
		u[i]=tmp;
	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++)
	{
		//cerr<<i<<" t "<<tab[i].l<<" "<<tab[i].r<<"\n";
		ans+=tab[i].size()*tab[i].size()-tab[i].common(tab[i-1])*tab[i].common(tab[i-1]);
		try_insert(i,n);
	}
	for(ki=n;ki>k;ki--)
	{
		int x=(pq.begin()->se);
		//cerr<<x<<"\n";
		//pq.erase(pq.begin());
		ans+=cost(x,n);
		//try_insert(u[x-1].fi,n);
		//try_insert(u[x+1].se,n);
		for(i=1;i<=n;i++)
			try_insert(i,n);
		upd(x,n);
		for(i=1;i<=n;i++)
			try_insert(i,n);
	}
	//for(i=1;i<=n;i=u[i].se+1)
	//	cout<<"i "<<tab[i].l<<" "<<tab[u[i].se].r<<"\n";
    return ans;
}

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