Submission #390806

#	Time	Username	Problem	Language	Result	Execution time	Memory
390806		tinjyu	Meetings (IOI18_meetings)	C++14	19 / 100	798 ms	216136 KiB

meetings

#include "meetings.h"
#include <iostream>
using namespace std;
long long int point[5005][5005][2],tree[1000005][3],he[1000005],len[1000005],temp[1000005][3],st,en;
int build(int s,int e,int t)
{
	if(s==e)
	{
		if(he[s]==1)
		{
			tree[t][0]=1;
			tree[t][1]=1;
			tree[t][2]=1;
		}
		return 0;
	}
	else 
	{
		build(s,(s+e)/2,t*2);
		build((s+e)/2+1,e,t*2+1);
		tree[t][0]=max(tree[t*2][0],max(tree[t*2+1][0],tree[t*2][2]+tree[t*2+1][1]));
		if(tree[t*2][1]==(s+e)/2-s+1)
		{
			tree[t][1]=tree[t*2][1]+tree[t*2+1][1];
		}
		else tree[t][1]=tree[t*2][1];
		if(tree[t*2+1][2]==e-(s+e)/2)
		{
			tree[t][2]=tree[t*2][2]+tree[t*2+1][2];
		}
		else tree[t][2]=tree[t*2+1][2];
	}
}
int find(int s,int e,int t)
{
	if(e<st || s>en)
	{
		temp[t][0]=0;
		temp[t][1]=0;
		temp[t][2]=0;
		len[t]=1;
		return 0;
	}
	if(st<=s && e<=en)
	{
		temp[t][0]=tree[t][0];
		temp[t][1]=tree[t][1];
		temp[t][2]=tree[t][2];
		len[t]=e-s+1;
		return 0;
	}
	find(s,(s+e)/2,t*2);
	find((s+e)/2+1,e,t*2+1);
	len[t]=len[t*2]+len[t*2+1];
	temp[t][0]=max(temp[t*2][0],max(temp[t*2+1][0],temp[t*2][2]+temp[t*2+1][1]));
	if(temp[t*2][1]==len[t*2])
	{
		temp[t][1]=temp[t*2][1]+temp[t*2+1][1];
	}
	else temp[t][1]=temp[t*2][1];
	if(temp[t*2+1][2]==len[t*2+1])
	{
		temp[t][2]=temp[t*2][2]+temp[t*2+1][2];
	}
	else temp[t][2]=temp[t*2+1][2];
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l, std::vector<int> r) {
	int q = l.size();
	int n = h.size();
	if(n<=5000 && q<=5000)
	{
	for(int i=0;i<n;i++)
	{
		int tmp=h[i];
		point[i][i][1]=h[i];
		for(int j=i+1;j<n;j++)
		{
			tmp=max(tmp,h[j]);
			point[i][j][1]=point[i][j-1][1]+tmp;
		}
  	}
  	for(int i=n-1;i>=0;i--)
  	{
  		int tmp=h[i];
  		point[i][i][0]=h[i];
  		for(int j=i-1;j>=0;j--)
  		{
  			tmp=max(tmp,h[j]);
  			 
  			point[j][i][0]=point[j+1][i][0]+tmp;
			//cout<<i<<" "<<j<<" "<<point[j][i][0]<<"  ";
		}
		//cout<<endl;
	}
  	std::vector<long long> c(q);
  	for(int i=0;i<q;i++)
  	{
  		long long int tmp=999999999999999999;
  		for(int j=l[i];j<=r[i];j++)
  		{
  			if(point[l[i]][j][0]+point[j][r[i]][1]-h[j]<tmp)
  			{
  				c[i]=j;
  				tmp=point[l[i]][j][0]+point[j][r[i]][1]-h[j];
				//cout<<tmp<<" "<<j<<" "<<point[l[i]][j][0]<<" "<<point[j][r[i]][1]<<"  ";
			}
		}
		c[i]=tmp;
		//cout<<endl;
	}
	return c;
	}
	else
	{
		build(0,n-1,1);
		for(int i=0;i<n;i++)he[i]=h[i];
		std::vector<long long> c(q);
		for(int i=0;i<q;i++)
		{
			st=l[i],en=r[i];
			long long int len=0,now=0;
			find(0,n-1,1);
			c[i]=(r[i]-l[i]+1)*2-temp[1][0];
		}
		return c;
	}
	
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:121:18: warning: unused variable 'len' [-Wunused-variable]
  121 |    long long int len=0,now=0;
      |                  ^~~
meetings.cpp:121:24: warning: unused variable 'now' [-Wunused-variable]
  121 |    long long int len=0,now=0;
      |                        ^~~
meetings.cpp: In function 'int build(int, int, int)':
meetings.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^
meetings.cpp: In function 'int find(int, int, int)':
meetings.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40