oj.uz

Submission #422135

# Submission time Handle Problem Language Result Execution time Memory
422135 2021-06-09T18:35:30 Z Jasiekstrz Meetings (IOI18_meetings) C++17
100 / 100
 4950 ms 213536 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 69196 KB Output is correct
2 Correct 36 ms 69596 KB Output is correct
3 Correct 35 ms 69612 KB Output is correct
4 Correct 35 ms 69572 KB Output is correct
5 Correct 34 ms 69588 KB Output is correct
6 Correct 36 ms 69572 KB Output is correct
7 Correct 34 ms 69612 KB Output is correct
8 Correct 34 ms 69552 KB Output is correct
9 Correct 33 ms 69568 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 69196 KB Output is correct
2 Correct 36 ms 69596 KB Output is correct
3 Correct 35 ms 69612 KB Output is correct
4 Correct 35 ms 69572 KB Output is correct
5 Correct 34 ms 69588 KB Output is correct
6 Correct 36 ms 69572 KB Output is correct
7 Correct 34 ms 69612 KB Output is correct
8 Correct 34 ms 69552 KB Output is correct
9 Correct 33 ms 69568 KB Output is correct
10 Correct 43 ms 70328 KB Output is correct
11 Correct 42 ms 70376 KB Output is correct
12 Correct 44 ms 70376 KB Output is correct
13 Correct 43 ms 70396 KB Output is correct
14 Correct 43 ms 70388 KB Output is correct
15 Correct 39 ms 70352 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 69200 KB Output is correct
2 Correct 96 ms 73540 KB Output is correct
3 Correct 441 ms 90108 KB Output is correct
4 Correct 337 ms 90372 KB Output is correct
5 Correct 357 ms 89368 KB Output is correct
6 Correct 362 ms 89088 KB Output is correct
7 Correct 400 ms 89216 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 69200 KB Output is correct
2 Correct 96 ms 73540 KB Output is correct
3 Correct 441 ms 90108 KB Output is correct
4 Correct 337 ms 90372 KB Output is correct
5 Correct 357 ms 89368 KB Output is correct
6 Correct 362 ms 89088 KB Output is correct
7 Correct 400 ms 89216 KB Output is correct
8 Correct 374 ms 89056 KB Output is correct
9 Correct 326 ms 89040 KB Output is correct
10 Correct 368 ms 89024 KB Output is correct
11 Correct 357 ms 89056 KB Output is correct
12 Correct 317 ms 88988 KB Output is correct
13 Correct 337 ms 88808 KB Output is correct
14 Correct 487 ms 89784 KB Output is correct
15 Correct 337 ms 88684 KB Output is correct
16 Correct 378 ms 87748 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 69196 KB Output is correct
2 Correct 36 ms 69596 KB Output is correct
3 Correct 35 ms 69612 KB Output is correct
4 Correct 35 ms 69572 KB Output is correct
5 Correct 34 ms 69588 KB Output is correct
6 Correct 36 ms 69572 KB Output is correct
7 Correct 34 ms 69612 KB Output is correct
8 Correct 34 ms 69552 KB Output is correct
9 Correct 33 ms 69568 KB Output is correct
10 Correct 43 ms 70328 KB Output is correct
11 Correct 42 ms 70376 KB Output is correct
12 Correct 44 ms 70376 KB Output is correct
13 Correct 43 ms 70396 KB Output is correct
14 Correct 43 ms 70388 KB Output is correct
15 Correct 39 ms 70352 KB Output is correct
16 Correct 29 ms 69200 KB Output is correct
17 Correct 96 ms 73540 KB Output is correct
18 Correct 441 ms 90108 KB Output is correct
19 Correct 337 ms 90372 KB Output is correct
20 Correct 357 ms 89368 KB Output is correct
21 Correct 362 ms 89088 KB Output is correct
22 Correct 400 ms 89216 KB Output is correct
23 Correct 374 ms 89056 KB Output is correct
24 Correct 326 ms 89040 KB Output is correct
25 Correct 368 ms 89024 KB Output is correct
26 Correct 357 ms 89056 KB Output is correct
27 Correct 317 ms 88988 KB Output is correct
28 Correct 337 ms 88808 KB Output is correct
29 Correct 487 ms 89784 KB Output is correct
30 Correct 337 ms 88684 KB Output is correct
31 Correct 378 ms 87748 KB Output is correct
32 Correct 3790 ms 201032 KB Output is correct
33 Correct 3233 ms 206532 KB Output is correct
34 Correct 3390 ms 194872 KB Output is correct
35 Correct 3909 ms 206540 KB Output is correct
36 Correct 3474 ms 206556 KB Output is correct
37 Correct 3760 ms 205468 KB Output is correct
38 Correct 4950 ms 213536 KB Output is correct
39 Correct 4578 ms 213528 KB Output is correct
40 Correct 2812 ms 194744 KB Output is correct
41 Correct 3619 ms 194856 KB Output is correct
42 Correct 3780 ms 194728 KB Output is correct
43 Correct 3884 ms 194824 KB Output is correct
44 Correct 4054 ms 194760 KB Output is correct