Submission #446910

#	Time	Username	Problem	Language	Result	Execution time	Memory
446910		Jasiekstrz	3D Histogram (COCI20_histogram)	C++17	110 / 110	2150 ms	28168 KiB

histogram

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int PP=27e4;
const long long INF=1e18L+7;
struct F
{
	long long a,b;
	long long operator()(long long x)
	{
		return a*x+b;
	}
};
long long when_greater(F &f1,F &f2)
{
	if(f1.b>=f2.b)
		return 0;
	if(f1.a<=f2.a)
		return INF;
	return (f2.b-f1.b+f1.a-f2.a-1)/(f1.a-f2.a);
}
int t[2][N+10];
int pa[N+10];
int pb[N+10];
int pot;
F tree[2*PP+10];
priority_queue<pair<long long,int>> pq;
long long read(int l,int r,long long x)
{
	long long ans=0;
	for(l+=pot,r+=pot;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans=max(ans,tree[l++](x));
		if(r%2==0)
			ans=max(ans,tree[r--](x));
	}
	return ans;
}
void change(int g,long long x)
{
	if(tree[2*g](x)<tree[2*g+1](x))
		return;
	tree[g]=tree[2*g];
	for(g/=2;g>0;g/=2)
	{
		if(tree[2*g](x)>=tree[2*g+1](x))
			tree[g]=tree[2*g];
		else
		{
			tree[g]=tree[2*g+1];
			pq.emplace(-when_greater(tree[2*g],tree[2*g+1]),g);
		}
	}
	return;
}
long long solve(int l,int r,int mid)
{
	pa[mid+1]=t[0][mid+1]; pb[mid+1]=t[1][mid+1];
	for(int i=mid+2;i<=r;i++)
	{
		pa[i]=min(pa[i-1],t[0][i]);
		pb[i]=min(pb[i-1],t[1][i]);
	}
	pa[mid]=t[0][mid]; pb[mid]=t[1][mid];
	for(int i=mid-1;i>=l;i--)
	{
		pa[i]=min(pa[i+1],t[0][i]);
		pb[i]=min(pb[i+1],t[1][i]);
	}
	//for(int i=l;i<=r;i++)
	//	cerr<<"("<<t[0][i]<<","<<t[1][i]<<")"<<" \n"[i==r];
	//for(int i=l;i<=r;i++)
	//	cerr<<"("<<pa[i]<<","<<pb[i]<<")"<<" \n"[i==r];

	for(pot=1;pot<=r-l+1;pot*=2);
	for(int i=1;i<=2*pot;i++)
		tree[i]={0,0};
	while(!pq.empty())
		pq.pop();
	for(int i=mid+1;i<=r;i++)
		tree[pot+i-l]={pb[i],(long long)pb[i]*(i-mid)};
	for(int i=pot-1;i>=1;i--)
	{
		tree[i]=tree[2*i+1];
		pq.emplace(-when_greater(tree[2*i],tree[2*i+1]),i);
	}
	long long ans=0;
	for(int i=mid,j=mid;i>=l;i--)
	{
		while(j<r && pa[j+1]>=pa[i] && pb[j+1]>=pb[i])
			j++;
		ans=max(ans,(long long)pa[i]*pb[i]*(j-i+1));
		//cerr<<i<<" "<<j<<" "<<ans<<"\n";
	}
	//cerr<<pot<<"\n";
	//for(int i=1;i<2*pot;i++)
	//	cerr<<i<<" "<<tree[i].a<<" "<<tree[i].b<<"\n";
	for(int i=mid,bg=mid+1,en=mid;i>=l;i--)
	{
		while(en<r && pa[en+1]>=pa[i])
			en++;
		while(bg<=en && pb[bg]>=pb[i])
			bg++;
		while(!pq.empty() && -pq.top().fi<=mid-i+1)
		{
			int x=pq.top().se;
			//cerr<<x<<"\n";
			pq.pop();
			change(x,mid-i+1);
		}
		//cerr<<tree[5].a<<" "<<tree[5].b<<"\n";
		ans=max(ans,(long long)pa[i]*read(bg-l,en-l,mid-i+1));
		//cerr<<i<<" "<<bg<<" "<<en<<" "<<ans<<"\n";
	}
	//cerr<<l<<" "<<r<<" "<<mid<<" "<<ans<<"\n\n";
	return ans;
}
long long dc(int l,int r)
{
	if(l>r)
		return 0;
	if(l==r)
		return (long long)t[0][l]*t[1][l];
	int mid=(l+r)/2;
	long long ans=max(dc(l,mid),dc(mid+1,r));
	for(int i:{0,1})
	{
		ans=max(ans,solve(l,r,mid));
		reverse(t[0]+l,t[0]+r+1);
		reverse(t[1]+l,t[1]+r+1);
		mid=r-(mid-l)-1;
	}
	//cerr<<l<<" "<<r<<" "<<ans<<"\n";
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>t[0][i]>>t[1][i];
	cout<<dc(1,n)<<"\n";
	return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'long long int dc(int, int)':
histogram.cpp:129:10: warning: unused variable 'i' [-Wunused-variable]
  129 |  for(int i:{0,1})
      |          ^

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