oj.uz

Submission #472547

# Submission time Handle Problem Language Result Execution time Memory
472547 2021-09-13T17:40:02 Z CaroLinda 3D Histogram (COCI20_histogram) C++14
0 / 110
 20 ms 22448 KB 
	#include <bits/stdc++.h>	
 	
#define sz(x) (int)(x.size())	
#define debug 	
#define ll long long	
#define all(x) x.begin(),x.end()	
 	
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) ; }	
    bool operator < ( Point other ) const { return make_pair(x,-y )< make_pair(other.x, -other.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 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 ;	
	}	
		
	vector<Point> v ;	
	for(int i = l ; i <= r ; i++ ) v.push_back(p[i]) ;	
		
    sort(all(v)) ;	 	
    vector<Point> convex ;	
 	
    for(int i = 1 ; i >= -1 ; i -= 2 )	
    {	
        int z = sz(convex) ;	
        for(auto j : v )	
        {	
            int zz = sz(convex) ;	
 	
            while( zz - 2 >= z &&  (convex[zz-1] - convex[zz-2]) % (j - convex[zz-2] ) <= 0 )	
                convex.pop_back() , zz-- ;	
 	
            convex.emplace_back(j) ;	
 	
        }	
 	
        convex.pop_back() ;	
        reverse(all(v)) ;	
 	
    }	
 	
    cht[pos] = convex ;	
		
	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  )	
	{	
		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 ] > px*cht[pos][ptr[pos]] )	
	{	
		ptr[pos]++ ;	
		if(ptr[pos] == tam ) ptr[pos] = 0 ;	
	}	
		
	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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22348 KB Output is correct
2 Correct 19 ms 22376 KB Output is correct
3 Correct 20 ms 22384 KB Output is correct
4 Incorrect 20 ms 22448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22348 KB Output is correct
2 Correct 19 ms 22376 KB Output is correct
3 Correct 20 ms 22384 KB Output is correct
4 Incorrect 20 ms 22448 KB Output isn't correct
5 Halted 0 ms 0 KB -