#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{
deque<line> hull;
void addline(line L){
while(sz(hull) >= 2){
if(cross(hull[sz(hull)-1], L) < cross(hull[sz(hull)-2], L)) hull.pop_back();
}
if(hull.empty() or hull.back().m != L.m) hull.push_back(L);
else hull.back().c = max(hull.back().c, L.c);
}
lint query(int x){
if(hull.empty()) return 0;
while(sz(hull) >= 2){
if(eval(hull[0], x) < eval(hull[1], x)) hull.pop_front();
else break;
}
return eval(hull[0], x);
}
};
lint ans = 0;
lint a[200005], b[200005], A[200005], B[200005]; ///A,B are raw value. a,b are for the prefix/suffix max
int n;
int N = 1000002;
convexhull seg[2000005];
void update(line L, int i){
for(i += N;i > 0;i >>= 1) seg[i].addline(L);
}
lint query(int l, int r, int 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]);
}
//if(s == 1 and e == n) for(int i = 1;i <= n;i++) cout << a[i] << " " << b[i] << endl;
///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
}
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];
dnc(1, n);
swap(A,B);
dnc(1, n);
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
262 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
262 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
