Submission #422135

#	Time	Username	Problem	Language	Result	Execution time	Memory
422135		Jasiekstrz	Meetings (IOI18_meetings)	C++17	100 / 100	4950 ms	213536 KiB

meetings

#include<bits/stdc++.h>
#include "meetings.h"
#define fi first
#define se second
using namespace std;
const int NN=75e4;
const int PP=11e5;
const long long INF=(long long)1e18+7;
struct Maxtree
{
	int pot;
	long long t[2*PP+10];
	void init(int n)
	{
		for(pot=1;pot<n;pot*=2);
		for(int i=1;i<=2*pot;i++)
			t[i]=-INF;
		return;
	}
	void leaf(int a,long long b)
	{
		t[pot+a-1]=b;
		return;
	}
	void build()
	{
		for(int i=pot-1;i>=1;i--)
			t[i]=max(t[2*i],t[2*i+1]);
		return;
	}
	long long read(int l,int r)
	{
		long long ans=-INF;
		for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
		{
			if(l%2==1)
				ans=max(ans,t[l++]);
			if(r%2==0)
				ans=max(ans,t[r--]);
		}
		return ans;
	}
};
struct Tree
{
	int pot;
	pair<long long,long long> t[2*PP+10];
	long long ad[2*PP+10];
	bool has_i[2*PP+10];
	int s[2*PP+10];
	void init(int n)
	{
		for(pot=1;pot<n;pot*=2);
		for(int i=1;i<=2*pot;i++)
		{
			t[i]={0,0};
			ad[i]=0;
			has_i[i]=false;
		}
		for(int i=pot;i<2*pot;i++)
			s[i]=1;
		for(int i=pot-1;i>0;i--)
			s[i]=s[2*i]+s[2*i+1];
		return;
	}
	void push_down(int i)
	{
		if(has_i[i])
		{
			ad[2*i]=ad[2*i+1]=0;
			has_i[2*i]=has_i[2*i+1]=true;
			t[2*i]=t[i];
			t[2*i+1]={t[i].fi+t[i].se*s[2*i],t[i].se};
		}
		ad[2*i]+=ad[i];
		ad[2*i+1]+=ad[i];
		ad[i]=0;
		has_i[i]=false;
		return;
	}
	void upd(int i,int l,int r,int ls,int rs,long long a,long long b)
	{
		if(ls<=l && r<=rs)
		{
			ad[i]=0;
			t[i]={a+b*(l-ls),b};
			has_i[i]=true;
			return;
		}
		push_down(i);
		int mid=(l+r)/2;
		if(ls<=mid)
			upd(2*i,l,mid,ls,rs,a,b);
		if(mid+1<=rs)
			upd(2*i+1,mid+1,r,ls,rs,a,b);
		return;
	}
	void add(int i,int l,int r,int ls,int rs,long long c)
	{
		if(ls<=l && r<=rs)
		{
			ad[i]+=c;
			return;
		}
		push_down(i);
		int mid=(l+r)/2;
		if(ls<=mid)
			add(2*i,l,mid,ls,rs,c);
		if(mid+1<=rs)
			add(2*i+1,mid+1,r,ls,rs,c);
		return;
	}
	long long read(int x)
	{
		for(int i=1,l=1,r=pot;l<r;)
		{
			push_down(i);
			int mid=(l+r)/2;
			if(x<=mid)
			{
				i=2*i;
				r=mid;
			}
			else
			{
				i=2*i+1;
				l=mid+1;
			}
		}
		return t[x+pot-1].fi+ad[x+pot-1];
	}
};
struct Que
{
	int l,r,id,mxh;
	bool operator<(const Que &oth)
	{
		return mxh<oth.mxh;
	}
};
Maxtree mxt;
Tree pref,suf;
vector<long long> que_ans;
//set<pair<int,int>> st;
int fau[NN+10];
pair<int,int> st[NN+10];
int fauf(int x)
{
	if(fau[x]!=x)
		fau[x]=fauf(fau[x]);
	return fau[x];
}
void fauu(int x,int y)
{
	x=fauf(x);y=fauf(y);
	st[x]={min(st[x].fi,st[y].fi),max(st[x].se,st[y].se)};
	fau[y]=x;
	return;
}
pair<int,int> un(pair<int,int> a,pair<int,int> b,long long h)
{
	if(a.fi==a.se || b.fi==b.se)
		return make_pair(a.fi,b.se);
	//cerr<<"("<<a.fi<<","<<a.se<<") ("<<b.fi<<","<<b.se<<")\n";
	long long x,y,z;
	int bg,en;
	// b prefix
	x=pref.read(a.se-1)+h;
	y=h;
	z=h*(a.se-a.fi);
	bg=b.fi;en=b.se;
	while(bg<en) // first where z better than xy
	{
		int mid=(bg+en)/2;
		if(z+pref.read(mid)<=x+y*(mid-b.fi))
			en=mid;
		else
			bg=mid+1;
	}
	if(b.fi<=bg-1)
		pref.upd(1,1,pref.pot,b.fi,bg-1,x,y);
	if(bg<=b.se-1)
		pref.add(1,1,pref.pot,bg,b.se-1,z);
	// a suffix
	x=suf.read(b.fi)+h*(a.se-a.fi);
	y=-h;
	z=h*(b.se-b.fi);
	bg=a.fi;en=a.se;
	while(bg<en) // first where xy better than z
	{
		int mid=(bg+en)/2;
		//cerr<<bg<<" "<<en<<" "<<mid<<"\n";
		if(z+suf.read(mid)>=x+y*(mid-a.fi))
			en=mid;
		else
			bg=mid+1;
	}
	if(bg<=a.se-1)
		suf.upd(1,1,suf.pot,bg,a.se-1,x+y*(bg-a.fi),y);
	//cerr<<"s u l="<<bg<<" r="<<a.se-1<<" "<<x+y*(bg-a.fi)<<" "<<y<<"\n";
	if(a.fi<=bg-1)
		suf.add(1,1,suf.pot,a.fi,bg-1,z);
	//cerr<<"s a l="<<a.fi<<" r="<<bg-1<<" "<<z<<"\n";
	return make_pair(a.fi,b.se);
}
void solve(vector<pair<int,int>> &ev,vector<Que> &qq)
{
	long long h=ev[0].fi;
	vector<pair<int,int>> t;
	for(auto v:ev)
	{
		//auto b=st.upper_bound({v.se,NN+10});
		auto b=st[fauf(v.se+1)];
		//auto a=prev(b);
		auto a=st[fauf(v.se)];
		if(t.empty() || t.back()!=a)
			t.push_back(a);
		t.push_back(b);
	}
	//cerr<<"t for h="<<h<<":\n";
	//for(auto v:t)
	//	cerr<<"("<<v.fi<<","<<v.se<<") ";
	//cerr<<"\n\n";
	mxt.init(t.size());
	for(size_t i=0;i<t.size();i++)
	{
		if(t[i].fi==t[i].se)
			mxt.leaf(i+1,0);
		else
			mxt.leaf(i+1,h*(t[i].se-t[i].fi)-pref.read(t[i].se-1));
	}
	mxt.build();
	for(auto v:qq)
	{
		que_ans[v.id]=h*(v.r-v.l+1);
		int bg,en;
		bg=0;en=t.size()-1;
		while(bg<en)
		{
			int mid=(bg+en)/2;
			if(t[mid].se<=v.l)
				bg=mid+1;
			else
				en=mid;
		}
		int a=bg;
		bg=0;en=t.size()-1;
		while(bg<en)
		{
			int mid=(bg+en+1)/2;
			if(t[mid].fi<=v.r)
				bg=mid;
			else
				en=mid-1;
		}
		int b=bg;
		long long w=max(mxt.read((a+1)+1,(b-1)+1),0LL);
		if(t[a].fi<t[a].se && t[a].se-1<=v.r)
		{
			int x=max(v.l,t[a].fi);
			w=max(w,h*(t[a].se-x)-suf.read(x));
			//cerr<<"a: "<<x<<" "<<w<<" "<<suf.read(x)<<"\n";
		}
		if(t[b].fi<t[b].se && v.l<=t[b].fi)
		{
			int x=min(v.r,t[b].se-1);
			w=max(w,h*(x-t[b].fi+1)-pref.read(x));
			//cerr<<"b: "<<x<<" "<<w<<"\n";
		}
		//cerr<<"qid="<<v.id<<" h="<<h<<" que_ans="<<que_ans[v.id]<<" w="<<w<<" a="<<a<<" b="<<b<<"\n";
		//cerr<<"t[a]=("<<t[a].fi<<","<<t[a].se<<")\n";
		//cerr<<"t[b]=("<<t[b].fi<<","<<t[b].se<<")\n";
		//cerr<<"\n";
		que_ans[v.id]-=w;
	}
	//for(auto v:t)
	//	st.erase(v);
	for(int i=ev.size()-1;i>=0;i--)
	{
		int v=ev[i].se;
		while(v+1<t.back().fi)
		{
			//st.insert(t.back());
			t.pop_back();
		}
		pref.upd(1,1,pref.pot,v,v,h,0);
		suf.upd(1,1,suf.pot,v,v,h,0);
		auto nw=un({v,v+1},t.back(),h);
		t.pop_back();
		nw=un(t.back(),nw,h);
		fauu(nw.fi,nw.se);
		t.pop_back();
		t.push_back(nw);
	}
	//while(!t.empty())
	//{
	//	st.insert(t.back());
	//	t.pop_back();
	//}
	return;
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R)
{
	int n=H.size();
	int q=L.size();
	vector<Que> qq(q);
	vector<pair<int,int>> ev(n);
	pref.init(n);
	suf.init(n);
	mxt.init(n);
	for(int i=0;i<n;i++)
		mxt.leaf(i+1,H[i]);
	mxt.build();
	que_ans.resize(q);
	for(int i=0;i<q;i++)
		qq[i]={L[i]+1,R[i]+1,i,(int)mxt.read(L[i]+1,R[i]+1)};
	sort(qq.begin(),qq.end());
	for(int i=0;i<n;i++)
		ev[i]={H[i],i+1};
	sort(ev.begin(),ev.end());
	for(int i=1;i<=n+1;i++)
	{
		//st.insert({i,i});
		fau[i]=i;
		st[i]={i,i};
	}
	vector<pair<int,int>> evtmp;
	vector<Que> qqtmp;
	for(int i=0,j=0;i<n;i++)
	{
		evtmp.clear();
		qqtmp.clear();
		for(;j<q && qq[j].mxh==ev[i].fi;j++)
			qqtmp.push_back(qq[j]);
		for(;i+1<n && ev[i+1].fi==ev[i].fi;i++)
			evtmp.push_back(ev[i]);
		evtmp.push_back(ev[i]);
		solve(evtmp,qqtmp);
	}
	return que_ans;
}

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