oj.uz

답안 #446910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446910 2021-07-23T18:44:31 Z Jasiekstrz 3D Histogram (COCI20_histogram) C++17
110 / 110
 2150 ms 28168 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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