Submission #471764

#	Time	Username	Problem	Language	Result	Execution time	Memory
471764		CaroLinda	3D Histogram (COCI20_histogram)	C++14	20 / 110	1022 ms	42364 KiB

histogram

#include <bits/stdc++.h>
 
#define sz(x) (int)(x.size())
#define debug 
#define ll long long
 
const int MAXN = 2e5+10 ;
 
using namespace std ;
 
struct Point
{
 
    ll x , y ;
 
    Point(ll x=0, ll y=0):x(x), y(y) {}
    
    Point operator - (Point other) const { return Point(x-other.x, y-other.y) ; } 
    ll operator % (Point other) const { return x*other.y - y*other.x ; }
    ll operator *(Point other) const { return x*other.x + y*other.y ; }
    void print() { printf("%lld %lld\n" , x , y) ; }
    void read() { scanf("%lld %lld", &x, &y) ; }
    int quadrant()
    {
        if(y >= 0 && x > 0) return 1 ;
        if( y > 0 && x <= 0 ) return 2 ;
        if( y <= 0 && x < 0 ) return 3 ;
        if( y < 0 && x <= 0 ) return 4 ;
        return 5 ; //origin
    }
} ;
 
int N ;
ll ans ; 
ll A[MAXN] , B[MAXN] , G[MAXN] , F[MAXN] ;
Point p[MAXN] ;
vector<Point> cht[MAXN*4] ;
int L[2] , R[2] , I[2] ;
int ptr[MAXN*4] ;
 
void build(int pos, int l, int r)
{
	cht[pos].clear() ;
	ptr[pos] = -1 ;
	
	if(r-l+1 <= 3 )
	{
		for(int i = l ; i <= r ; i++ ) cht[pos].push_back(p[i]) ;
		if(l == r ) return ;
		build(pos<<1 , l, (l+r)>>1 ) ;
		build(pos<<1|1 , (l+r+2)>>1 , r ) ;
		return ;
	}
	
	L[0] = r , R[0] = l-1 ;
	L[1] = l , R[1] = r+1 ;
	I[0] = -1 , I[1] = 1 ;
	
	for(int j = 0 , ant = 0; j < 2 ; j++, cht[pos].pop_back() , ant = sz(cht[pos]) )
		for(int i = L[j] ; i != R[j] ; i += I[j])
		{
			while( sz(cht[pos])-ant > 1  )
			{
				int q = sz(cht[pos]) ;
				if( (p[i]-cht[pos][q-2])%(cht[pos][q-1]-cht[pos][q-2]) > 0 ) break ;
				cht[pos].pop_back() ;
			}
			cht[pos].push_back(p[i]) ;
		}
	
	build(pos<<1 , l, (l+r)>>1 ) ;
	build(pos<<1|1 , (l+r+2)>>1 , r ) ;
	
}
 
void getAnswer(int pos, int l, int r, int beg, int en, Point px )
{
	if(l > en || r < beg ) return ;
	if( !(beg <= l && r <= en) )
	{
		getAnswer(pos<<1 , l, (l+r)>>1 , beg, en , px ) ;
		getAnswer( pos<<1|1 , (l+r+2)>>1 , r, beg, en , px ) ;
		return ;
	}
	if(cht[pos].empty()) return ;
	
	
	if( ptr[pos] == -1 || sz(cht[pos]) <= 3 || px.x == 0 || true )
	{
		ll cur = px*cht[pos][0] ;
		ptr[pos] = 0 ;
		for(int i = 1 ; i < sz(cht[pos]) ; i++ )
		{
			ll temp = px*cht[pos][i] ;
			if(temp <= cur) continue ;
			cur = temp ;
			ptr[pos] = i ;
		}
		ans = max(ans, cur) ;
		return ;
	}
	
	int tam = sz(cht[pos]) ;
	while( px*cht[pos][ (ptr[pos]-1+tam)%tam ] > px*cht[pos][ptr[pos]] )
	{
		ptr[pos]-- ;
		if(ptr[pos] == -1 ) ptr[pos] += tam ;
	}
	
	ans = max(ans, px*cht[pos][ptr[pos]] ) ;
	
}
 
void solve(int l, int r)
{
	if(l == r )
	{
		ans = max(ans, A[l]*B[l]) ;
		return ;
	}
	
	int mid = (l+r+1)>>1 ;
	
	F[mid-1] = A[mid-1] ;
	G[mid-1] = B[mid-1] ;
	for(int i = mid-2 ; i >= l ; i-- )
	{
		F[i] = min(F[i+1] , A[i] ) ;
		G[i] = min(G[i+1] , B[i] ) ;
	}
	
	F[mid] = A[mid] ;
	G[mid] = B[mid] ;
	for(int i = mid+1 ; i <= r ; i++ ) 
	{
		F[i] = min( F[i-1] , A[i] ) ;
		G[i] = min(G[i-1],B[i]) ;
	}
	for(int i = mid ; i <= r ; i++ ) p[i] = Point( G[i] , G[i]*(ll)i ) ;
	
	build(1,mid, r) ; 
	
	//Convex hull part
	int ptrF = mid , ptrG = mid ;
	for(int i = mid-1 ; i >= l ; i-- )
	{		
		while( ptrF <= r && F[ptrF] >= F[i] ) ptrF++ ;
		while( ptrG <= r && G[ptrG] > G[i] ) ptrG++ ;
		
		getAnswer( 1 , mid , r , ptrG, ptrF-1 , Point(F[i]*(1-i) , F[i] ) ) ;
		
		while( ptrG <= r && G[ptrG] >= G[i] ) ptrG++ ;
		ans = max(ans, F[i]*G[i]*( min(ptrF, ptrG) - i ) ) ;		
	}
	
	solve(l,mid-1) ;
	solve(mid, r) ;
}
 
int main()
{
	scanf("%d", &N ) ;
	for(int i = 1 ; i <= N ; i++ ) scanf("%lld %lld", &A[i], &B[i] ) ;
	
	solve(1,N) ;
	reverse(A+1, A+1+N) ;
	reverse(B+1, B+1+N ) ;
	solve(1,N) ;
	
	printf("%lld\n" , ans ) ;
	
}

Compilation message (stderr)

histogram.cpp: In function 'int main()':
histogram.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
histogram.cpp:163:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |  for(int i = 1 ; i <= N ; i++ ) scanf("%lld %lld", &A[i], &B[i] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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