Submission #446910

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
446910	2021-07-23T18:44:31 Z	Jasiekstrz	3D Histogram (COCI20_histogram)	C++17	110 / 110	2150 ms	28168 KB

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

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	536 KB	Output is correct
2	Correct	8 ms	508 KB	Output is correct
3	Correct	8 ms	460 KB	Output is correct
4	Correct	9 ms	588 KB	Output is correct
5	Correct	8 ms	552 KB	Output is correct
6	Correct	9 ms	460 KB	Output is correct
7	Correct	10 ms	460 KB	Output is correct
8	Correct	10 ms	460 KB	Output is correct
9	Correct	8 ms	620 KB	Output is correct
10	Correct	12 ms	532 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	8 ms	460 KB	Output is correct

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	536 KB	Output is correct
2	Correct	8 ms	508 KB	Output is correct
3	Correct	8 ms	460 KB	Output is correct
4	Correct	9 ms	588 KB	Output is correct
5	Correct	8 ms	552 KB	Output is correct
6	Correct	9 ms	460 KB	Output is correct
7	Correct	10 ms	460 KB	Output is correct
8	Correct	10 ms	460 KB	Output is correct
9	Correct	8 ms	620 KB	Output is correct
10	Correct	12 ms	532 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	8 ms	460 KB	Output is correct
13	Correct	1496 ms	19956 KB	Output is correct
14	Correct	1935 ms	19988 KB	Output is correct
15	Correct	1655 ms	19996 KB	Output is correct
16	Correct	1621 ms	19960 KB	Output is correct
17	Correct	2150 ms	28168 KB	Output is correct
18	Correct	1814 ms	19968 KB	Output is correct
19	Correct	1770 ms	19972 KB	Output is correct
20	Correct	1930 ms	19928 KB	Output is correct
21	Correct	1800 ms	19988 KB	Output is correct
22	Correct	2123 ms	28124 KB	Output is correct
23	Correct	131 ms	2320 KB	Output is correct
24	Correct	1638 ms	19952 KB	Output is correct