oj.uz

답안 #472536

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472536 2021-09-13T17:19:09 Z CaroLinda 3D Histogram (COCI20_histogram) C++14
0 / 110
 23 ms 22560 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]) ;
	
    if(sz(v) < 3) 
    {
    	cht[pos] = v ;
    	build(pos<<1 , l, (l+r)>>1 ) ;
		build(pos<<1|1 , (l+r+2)>>1 , r ) ;
		return ;
	}

    vector<Point> convex ;
    sort(all(v)) ;

    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] = v ;
	
	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:182:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
histogram.cpp:183:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |  for(int i = 1 ; i <= N ; i++ ) scanf("%lld %lld", &A[i], &B[i] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 22476 KB Output is correct
2 Correct 23 ms 22484 KB Output is correct
3 Correct 23 ms 22560 KB Output is correct
4 Incorrect 19 ms 22548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 22476 KB Output is correct
2 Correct 23 ms 22484 KB Output is correct
3 Correct 23 ms 22560 KB Output is correct
4 Incorrect 19 ms 22548 KB Output isn't correct
5 Halted 0 ms 0 KB -