Submission #446012

#	Time	Username	Problem	Language	Result	Execution time	Memory
446012		Jasiekstrz	3D Histogram (COCI20_histogram)	C++17	0 / 110	15 ms	19276 KiB

histogram

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int PP=27e4;
const int INF=1e9+7;
int n;
long long w=0;
int t[N+10][2];
int srt[N+10];
int fau[N+10];
int l[N+10];
int r[N+10];
int pr[N+10];
int nx[N+10];
set<int> mnpref[N+10];
set<int> mnsuf[N+10];
int pot;
int tree[2*PP+10];
int findr(int x,int c)
{
	x+=pot;
	while(x>0 && tree[x]>=c)
	{
		if(x%2==1)
			x++;
		x/=2;
	}
	while(x<pot)
	{
		if(tree[2*x]<c)
			x=2*x;
		else
			x=2*x+1;
	}
	return x-pot;
}
int findl(int x,int c)
{
	x+=pot;
	while(x>0 && tree[x]>=c)
	{
		if(x%2==0)
			x--;
		x/=2;
	}
	while(x<pot)
	{
		if(tree[2*x+1]<c)
			x=2*x+1;
		else
			x=2*x;
	}
	return x-pot;
}
int f(int x)
{
	return (fau[x]==x ? x:fau[x]=f(fau[x]));
}
void setnx(int x,int c)
{
	nx[x]=c;
	if(mnpref[f(x)].find(x)!=mnpref[f(x)].end())
		pr[x]=l[f(x)];
	w=max(w,(long long)t[x][0]*(nx[x]-pr[x]+1));
	return;
}
void setpr(int x,int c)
{
	pr[x]=c;
	if(mnsuf[f(x)].find(x)!=mnsuf[f(x)].end())
		nx[x]=r[f(x)];
	w=max(w,(long long)t[x][0]*(nx[x]-pr[x]+1));
	return;
}
void u(int x,int y)
{
	x=f(x);
	y=f(y);
	if(r[x]-l[x]<r[y]-l[y]) // left one smaller
	{
		vector<int> st;
		for(int i=l[x];i<=r[x];i++)
		{
			while(!st.empty() && t[st.back()][0]>t[i][0])
				st.pop_back();
			st.push_back(i);
		}
		while(!mnpref[y].empty() && !st.empty())
		{
			if(t[st.back()][0]<t[*mnpref[y].begin()][0])
			{
				setpr(*mnpref[y].begin(),st.back()+1);
				mnpref[y].erase(mnpref[y].begin());
			}
			else
				st.pop_back();
		}
		for(auto v:mnpref[x])
			mnpref[y].insert(v);
		{set<int> ().swap(mnpref[x]);}
		while(!mnsuf[x].empty())
		{
			auto it=prev(mnsuf[x].end());
			int tmp=findr(*it,t[*it][0]);
			if(tmp>r[y])
				break;
			setnx(*it,tmp-1);
			mnsuf[x].erase(it);
		}
		for(auto v:mnsuf[x])
			mnsuf[y].insert(v);
		{set<int> ().swap(mnsuf[x]);}
		l[y]=l[x];
		fau[x]=y;
	}
	else // right one smaller
	{
		vector<int> st;
		for(int i=r[y];i>=l[y];i--)
		{
			while(!st.empty() && t[st.back()][0]>t[i][0])
				st.pop_back();
			st.push_back(i);
		}
		while(!mnsuf[x].empty() && !st.empty())
		{
			auto it=prev(mnsuf[x].end());
			if(t[st.back()][0]<t[*it][0])
			{
				setnx(*it,st.back()-1);
				mnsuf[x].erase(it);
			}
			else
				st.pop_back();
		}
		for(auto v:mnsuf[y])
			mnsuf[x].insert(v);
		{set<int> ().swap(mnsuf[y]);}
		while(!mnpref[y].empty())
		{
			auto it=mnpref[y].begin();
			int tmp=findl(*it,t[*it][0]);
			if(tmp<l[x])
				break;
			setpr(*it,tmp+1);
			mnpref[y].erase(it);
		}
		for(auto v:mnpref[y])
			mnpref[x].insert(v);
		{set<int> ().swap(mnpref[y]);}
		r[x]=r[y];
		fau[y]=x;
	}
	return;
}
void updw(int x)
{
	x=f(x);
	if(!mnpref[x].empty())
		setpr(*mnpref[x].begin(),l[x]);
	if(!mnsuf[x].empty())
		setnx(*prev(mnsuf[x].end()),r[x]);
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(pot=1;pot<=n+1;pot*=2);
	for(int i=1;i<=n;i++)
	{
		cin>>t[i][0]>>t[i][1];
		tree[pot+i]=t[i][0];
		srt[i]=i;
	}
	for(int i=pot-1;i>=1;i--)
		tree[i]=min(tree[2*i],tree[2*i+1]);
	sort(srt+1,srt+n+1,[](int a,int b){ return t[a][1]>t[b][1]; });
	long long ans=0;
	for(int qi=1;qi<=n;qi++)
	{
		fau[srt[qi]]=srt[qi];
		l[srt[qi]]=r[srt[qi]]=srt[qi];
		pr[srt[qi]]=nx[srt[qi]]=srt[qi];
		w=max(w,(long long)t[srt[qi]][0]);
		mnpref[srt[qi]].insert(srt[qi]);
		mnsuf[srt[qi]].insert(srt[qi]);
		if(fau[srt[qi]-1]!=0)
			u(srt[qi]-1,srt[qi]);
		if(fau[srt[qi]+1]!=0)
			u(srt[qi],srt[qi]+1);
		updw(srt[qi]);
		ans=max(ans,w*t[srt[qi]][1]);
	}
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 90