#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 <= N )
{
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]) <= N )
{
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: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] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
22476 KB |
Output is correct |
| 2 |
Correct |
14 ms |
22476 KB |
Output is correct |
| 3 |
Correct |
16 ms |
22428 KB |
Output is correct |
| 4 |
Correct |
19 ms |
22416 KB |
Output is correct |
| 5 |
Correct |
16 ms |
22476 KB |
Output is correct |
| 6 |
Correct |
20 ms |
22488 KB |
Output is correct |
| 7 |
Correct |
12 ms |
22476 KB |
Output is correct |
| 8 |
Correct |
14 ms |
22464 KB |
Output is correct |
| 9 |
Correct |
21 ms |
22476 KB |
Output is correct |
| 10 |
Correct |
17 ms |
22476 KB |
Output is correct |
| 11 |
Correct |
11 ms |
22256 KB |
Output is correct |
| 12 |
Correct |
14 ms |
22476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
22476 KB |
Output is correct |
| 2 |
Correct |
14 ms |
22476 KB |
Output is correct |
| 3 |
Correct |
16 ms |
22428 KB |
Output is correct |
| 4 |
Correct |
19 ms |
22416 KB |
Output is correct |
| 5 |
Correct |
16 ms |
22476 KB |
Output is correct |
| 6 |
Correct |
20 ms |
22488 KB |
Output is correct |
| 7 |
Correct |
12 ms |
22476 KB |
Output is correct |
| 8 |
Correct |
14 ms |
22464 KB |
Output is correct |
| 9 |
Correct |
21 ms |
22476 KB |
Output is correct |
| 10 |
Correct |
17 ms |
22476 KB |
Output is correct |
| 11 |
Correct |
11 ms |
22256 KB |
Output is correct |
| 12 |
Correct |
14 ms |
22476 KB |
Output is correct |
| 13 |
Execution timed out |
2574 ms |
66172 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
