#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)%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
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] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
22476 KB |
Output is correct |
| 2 |
Correct |
19 ms |
22476 KB |
Output is correct |
| 3 |
Correct |
18 ms |
22476 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
22476 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
22476 KB |
Output is correct |
| 2 |
Correct |
19 ms |
22476 KB |
Output is correct |
| 3 |
Correct |
18 ms |
22476 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
22476 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
