Submission #279555

#	Time	Username	Problem	Language	Result	Execution time	Memory
279555		tinjyu	Aliens (IOI16_aliens)	C++14	100 / 100	218 ms	10288 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
	long long int x,y;
}a[1000005];
long long int dp[1000005],x[1000005],y[1000005],t[1000005][3],g[1000005],mi,minum,ma=999999999999999,manum;
bool cmp(node a,node b)
{
	if(a.x<b.x)return 1;
	if(a.x>b.x)return 0;
	if(a.y>a.y)return 1;
	return 0;
}
double check(long long int a,long long int b)
{
	if(t[a][1]==t[b][1])return 99999999999999;
	return (t[a][0]-t[b][0])/(t[a][1]-t[b][1]);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for(int i=0;i<n;i++)
    {
    	a[i].x=r[i];
    	a[i].y=c[i];
    	if(a[i].y<a[i].x)
    	{
    		swap(a[i].x,a[i].y);
		}
	}
	sort(a,a+n,cmp);
	long long int cnt=1;
	x[1]=a[0].x;
	y[1]=a[0].y;
	for(int i=1;i<n;i++)
	{
		if(a[i].x>x[cnt] && a[i].y>y[cnt])
		{
			cnt++;
			x[cnt]=a[i].x;
			y[cnt]=a[i].y;
		}
		else if(a[i].x==x[cnt] && a[i].y>y[cnt])
		{
			x[cnt]=a[i].x;
			y[cnt]=a[i].y;
		}
	}
	n=cnt;
	//cout<<n<<endl;	
	//for(int i=1;i<=n;i++)cout<<x[i]<<" "<<y[i]<<endl;
	//system("pause");		
	
	if(k>n)k=n;
	x[0]=0;
	y[0]=0;
	long long int le=0,ri=(long long int)m*(long long int)m,ans;
	while(le<=ri)
	{
		long long int mid=(le+ri)/2;
		int st=0,en=0;
		

		//cout<<mid<<endl;
		dp[1]=0;
		t[0][0]=(x[1]-1)*(x[1]-1);
		t[0][1]=x[1]-1;
		t[0][2]=0;

		for(int i=1;i<=n;i++)
		{
			//cout<<i<<" "<<check(st,st+1)<<" "<<2*y[i]<<endl;
			while(en>=st+1 && check(st,st+1)<2*y[i])
			{
				st++;
			}
			int p=t[st][2];
			//cout<<st<<" "<<p<<endl;
			if(y[p]-x[p+1]+1>0 && p!=0)dp[i]=mid+dp[p]+(y[i]-x[p+1]+1)*(y[i]-x[p+1]+1)-(y[p]-x[p+1]+1)*(y[p]-x[p+1]+1);
			else dp[i]=mid+dp[p]+(y[i]-x[p+1]+1)*(y[i]-x[p+1]+1);
			g[i]=g[p]+1;
			en++;
			//cout<<dp[i]+(x[i+1]-1)*(x[i+1]-1)<<endl;
			t[en][0]=dp[i]+(x[i+1]-1)*(x[i+1]-1)-max((long long int)0,y[i]-x[i+1]+1)*max((long long int)0,y[i]-x[i+1]+1);
			t[en][1]=x[i+1]-1;
			t[en][2]=i;
			while(en>=st+2 && check(en,en-2)<check(en-1,en-2))
			{
				en--;
				t[en][0]=dp[i]+(x[i+1]-1)*(x[i+1]-1)-max((long long int)0,y[i]-x[i+1]+1)*max((long long int)0,y[i]-x[i+1]+1);
				t[en][1]=x[i+1]-1;
				t[en][2]=i;
			}
			//for(int j=st;j<=en;j++)cout<<" "<<t[j][0]<<" "<<t[j][1]<<" "<<t[j][2]<<endl;
 
			//cout<<dp[i]<<" "<<g[i]<<" "<<p<<endl;
		}
		//cout<<mid<<" "<<g[n]<<" "<<dp[n]<<endl;
		//cout<<endl;
		if(g[n]<=k)
		{
			if(g[n]>mi)
			{
				mi=g[n];
				minum=dp[n]-mid*g[n];
			}
			if(g[n]==k)return dp[n]-mid*g[n];
			ri=mid-1;
		}
		else 
		{
			le=mid+1;
			if(g[n]<ma)
			{
				ma=g[n];
				manum=dp[n]-mid*g[n];
			}
		}
	}
	//cout<<mi<<" "<<minum<<" "<<ma<<" "<<manum<<endl;
	return (long long int)(manum+(ma-k)*(minum-manum)/(ma-mi));
}

Compilation message (stderr)

aliens.cpp: In function 'bool cmp(node, node)':
aliens.cpp:13:8: warning: self-comparison always evaluates to false [-Wtautological-compare]
   13 |  if(a.y>a.y)return 1;
      |     ~~~^~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:57:58: warning: unused variable 'ans' [-Wunused-variable]
   57 |  long long int le=0,ri=(long long int)m*(long long int)m,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