#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define m first
#define c second
#define show(x) cerr << #x << " is " << x << endl;
typedef long long lint;
typedef long double lida;
typedef pair<lint,lint> line;
lint eval(line L, lint x){ return L.m * x + L.c; }
lida cross(line a, line b){ return (lida) (a.c-b.c) / (lida) (b.m-a.m); }
struct convexhull{
vector<line> hull;
void addline(line L){
if(hull.empty() or hull.back().m != L.m) hull.push_back(L);
else hull.back().c = max(hull.back().c, L.c);
while(sz(hull) >= 3){
int S = sz(hull);
if(cross(hull[S-3], hull[S-1]) < cross(hull[S-2], hull[S-3])){
hull[S-2] = hull[S-1];
hull.pop_back();
}
else break;
}
}
lint query(lint x){
if(hull.empty()) return 0;
while(sz(hull) >= 2){
if(eval(hull[sz(hull)-2],x) > eval(hull[sz(hull)-1], x)) hull.pop_back();
else break;
}
return eval(hull.back(), x);
}
void clear(){ hull.clear(); }
};
lint ans = 0;
lint a[200005], b[200005], A[200005], B[200005]; ///A,B are raw value. a,b are for the prefix/suffix min
int n;
int dis[1000005];
int N = 200002;
convexhull seg[400005];
void update(line L, int i){
for(i += N;i > 0;i >>= 1) seg[i].addline(L);
}
void reset(int i){
for(i += N;i > 0;i >>= 1) seg[i].clear();
}
lint query(int l, int r, lint x){
lint res = 0;
for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
if(l&1) res = max(res, seg[l++].query(x));
if(r&1) res = max(res, seg[--r].query(x));
}
return res;
}
void dnc(int s, int e){
if(s == e){
ans = max(ans, A[s]*B[s]);
return;
}
int m = (s+e)/2;
dnc(s,m); dnc(m+1,e);
a[m] = A[m], b[m] = B[m], a[m+1] = A[m+1], b[m+1] = B[m+1];
for(int i = m-1;i >= s;i--){
a[i] = min(a[i+1], A[i]);
b[i] = min(b[i+1], B[i]);
}
for(int i = m+2;i <= e;i++){
a[i] = min(a[i-1], A[i]);
b[i] = min(b[i-1], B[i]);
}
///a, b both on left side
int r = e;
for(int l = s;l <= m;l++){
while(r >= m+1){
if(a[l] > a[r] or b[l] > b[r]) r--;
else break;
}
if(r == m) break;
ans = max(ans, (r-l+1) * a[l] * b[l]);
}
///a on left and b on right
r = e;
for(int l = s;l <= m;l++){
while(r >= m+1){
if(a[l] >= a[r]){
update(line(a[r], (r+1)*a[r]), dis[b[r]]); ///a[r] increasing going to the left
r--;
}
else break;
}
lint res = query(dis[b[l]], N-1, -l); ///-l decreasing going to the right
res *= b[l];
ans = max(ans, res);
}
for(int r = m+1;r <= e;r++) reset(dis[b[r]]);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++) cin >> A[i] >> B[i];
for(int i = 1;i <= n;i++) dis[B[i]] = 1;
for(int i = 1;i <= 1000000;i++) dis[i] += dis[i-1];
dnc(1, n);
reverse(A+1,A+n+1);
reverse(B+1,B+n+1);
dnc(1, n);
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
13764 KB |
Output is correct |
| 2 |
Correct |
14 ms |
13828 KB |
Output is correct |
| 3 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 4 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 5 |
Correct |
13 ms |
13828 KB |
Output is correct |
| 6 |
Correct |
14 ms |
13860 KB |
Output is correct |
| 7 |
Correct |
13 ms |
13840 KB |
Output is correct |
| 8 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 9 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 10 |
Correct |
14 ms |
13772 KB |
Output is correct |
| 11 |
Incorrect |
9 ms |
13644 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
13764 KB |
Output is correct |
| 2 |
Correct |
14 ms |
13828 KB |
Output is correct |
| 3 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 4 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 5 |
Correct |
13 ms |
13828 KB |
Output is correct |
| 6 |
Correct |
14 ms |
13860 KB |
Output is correct |
| 7 |
Correct |
13 ms |
13840 KB |
Output is correct |
| 8 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 9 |
Correct |
13 ms |
13644 KB |
Output is correct |
| 10 |
Correct |
14 ms |
13772 KB |
Output is correct |
| 11 |
Incorrect |
9 ms |
13644 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
