Submission #102609

#	Time	Username	Problem	Language	Result	Execution time	Memory
102609		faustaadp	Meetings (IOI18_meetings)	C++17	36 / 100	1045 ms	7908 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
ll n,i,a[101010],ST[404040],ki[101010],ka[101010],P[5050],S[5050];
void upd(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(aa==bb)ST[ee]=dd;
	else
	{
		ll ce=(aa+bb)/2;
		if(cc<=ce)upd(aa,ce,cc,dd,ee*2);
		else upd(ce+1,bb,cc,dd,ee*2+1);
		ST[ee]=max(ST[ee*2],ST[ee*2+1]);
	}
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(bb<cc||dd<aa)return 0;
	else
	if(cc<=aa&&bb<=dd)return ST[ee];
	else
	{
		ll ce=(aa+bb)/2;
		return max(que(aa,ce,cc,dd,ee*2),que(ce+1,bb,cc,dd,ee*2+1));
	}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) 
{
	n=H.size();
	for(i=1;i<=n;i++)a[i]=H[i-1];
	for(i=1;i<=n;i++)
		if(a[i]==a[i-1])
			ki[i]=ki[i-1];
		else
			ki[i]=i;
	for(i=n;i>=1;i--)
		if(a[i]==a[i+1])
			ka[i]=ka[i+1];
		else
			ka[i]=i;
	for(i=1;i<=n;i++)
		if(a[i]==1)
			upd(1,n,i,ka[i]-ki[i]+1,1);
  	int Q = L.size();
  	std::vector<long long> C(Q);
  	for (int j = 0; j < Q; ++j) 
  	{
  		L[j]++;
  		R[j]++;
  		if(Q<=5000&&n<=5000)
  		{
  			C[j]=1e18;
  			{
	  			stack<pair<ll,ll> > st;
	  			P[L[j]-1]=0;
	  			for(i=L[j];i<=R[j];i++)
	  			{
	  				P[i]=P[i-1]+a[i];
	  				ll las=i;
	  				while(!st.empty()&&st.top().fi<=a[i])
	  				{
	  					P[i]-=(las-st.top().se)*st.top().fi;
	  					P[i]+=(las-st.top().se)*a[i];
	  					las=st.top().se;
	  					st.pop();
	  				}
	  				st.push(mp(a[i],las));
	  			}
	  		}
	  		{
	  			stack<pair<ll,ll> > st;
	  			S[R[j]+1]=0;
	  			for(i=R[j];i>=L[j];i--)
	  			{
	  				S[i]=S[i+1]+a[i];
	  				ll las=i;
	  				while(!st.empty()&&st.top().fi<=a[i])
	  				{
	  					//cout<<"_"<<i<<"\n";
	  					S[i]-=(st.top().se-las)*st.top().fi;
	  					S[i]+=(st.top().se-las)*a[i];
	  					las=st.top().se;
	  					st.pop();
	  				}
	  				st.push(mp(a[i],las));
	  				//cout<<i<<" "<<S[i]<<"\n";
	  			}
	  		}
	  		for(i=L[j];i<=R[j];i++)
	  			C[j]=min(C[j],P[i]+S[i]-a[i]);
  			continue;
  		}
  		//cout<<ka[L[j]]<<" "<<ki[R[j]]<<"\n";
  		C[j]=que(1,n,ka[L[j]]+1,ki[R[j]]-1,1);
  		//cout<<C[j]<<"_\n";
  		if(a[R[j]]==1&&ki[R[j]]>=L[j])C[j]=max(C[j],R[j]-ki[R[j]]+1);
  		else if(a[R[j]]==1)C[j]=max(C[j],R[j]-L[j]+1LL);
  		if(a[L[j]]==1&&ka[L[j]]<=R[j])C[j]=max(C[j],ka[L[j]]-L[j]+1);
  		else if(a[L[j]]==1)C[j]=max(C[j],R[j]-L[j]+1LL);
  		C[j]=2*(R[j]-L[j]+1)-C[j];
  	}
 	return C;
}

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