#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 200 * 1000 + 10;
int n;
int a[nax], b[nax], f[nax], g[nax];
struct Point {
ll x, y;
int id;
};
Point lines[nax];
ll ans;
vector<Point>S1, S2;
int ptr, last;
ll intersect(Point&x, Point&y, Point&z) {
return (z.x - x.x) * (y.y - x.y) - (y.x - x.x)*(z.y - x.y);
}
ll get_mx(vector<Point>&vec, int x) {
if((int)vec.size() == 0) return -1;
while((int)vec.size() >= 2 && (ll)vec.back().x * x + vec.back().y <= (ll)vec[(int)vec.size() - 2].x * x + vec[(int)vec.size() - 2].y) {
vec.pop_back();
}
return (ll)vec.back().x * x + vec.back().y;
}
ll get_mx2(int x) {
if((int)S2.size() == 0) return -1;
while(ptr + 1 < (int)S2.size() && S2[ptr+1].x * x + S2[ptr+1].y >= S2[ptr].x * x + S2[ptr].y) {
ptr++;
}
return S2[ptr].x * x + S2[ptr].y;
}
vi rem[nax];
void rec(int l, int r) {
int mid = ((l + r) >> 1);
if(l <= mid - 1) rec(l, mid - 1);
if(mid + 1 <= r) rec(mid + 1, r);
f[mid] = a[mid];
g[mid] = b[mid];
lines[mid] = {g[mid], (ll)g[mid] * mid, mid};
for(int i = mid - 1; i >= l; --i) {
f[i] = min(f[i + 1], a[i]);
g[i] = min(g[i + 1], b[i]);
lines[i] = {g[i], (ll)g[i] * (-i + 1), i};
}
for(int i = mid + 1; i <= r; ++i) {
f[i] = min(f[i - 1], a[i]);
g[i] = min(g[i - 1], b[i]);
lines[i] = {g[i], (ll)g[i] * i, i};
}
int lp, rp, l2, r2;
rp = r;
for(lp = l; lp <= mid; ++lp) {
while(rp >= mid && (f[lp] > f[rp] || g[lp] > g[rp])) {
rp--;
}
if(rp >= mid) {
ans = max(ans, (ll)f[lp] * g[lp] * (rp - lp + 1));
}
}
lp = l;
for(rp = r; rp >= mid; rp--) {
while(lp <= mid && (f[rp] > f[lp] || g[rp] > g[lp])) {
lp++;
}
if(lp <= mid) {
ans = max(ans, (ll)f[rp] * g[rp] * (rp - lp + 1));
}
}
// --------------------------
rp = r;
r2 = r;
S1.clear(); S2.clear();
last = r + 1;
ptr = 0;
S1.PB(lines[r]);
for(int i = mid; i <= r; ++i) rem[i].clear();
for(lp = l; lp <= mid; lp++) {
while(r2 - 1 >= mid && (g[lp] >= g[r2 - 1])) {
r2--;
if((int)S1.size() >= 1 && S1.back().x == lines[r2].x) continue;
while((int)S1.size() >= 2 && intersect(S1.back(), lines[r2], S1[(int)S1.size() - 2]) <= 0) {
S1.pop_back();
}
S1.PB(lines[r2]);
// add
}
while(rp >= mid && (f[lp] > f[rp])) {
rp--;
// erase
}
if(rp >= mid && g[lp] >= g[r2] && r2 <= rp) {
// [r2, rp]
while(S2.size() > 0 && S2.back().id >= rp + 1) {
if(ptr > 0) ptr--;
reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
int id = S2.back().id;
S2.pop_back();
for(int x : rem[id]) {
S2.PB(lines[x]);
}
// must add points
}
if((int)S1.size() > 0 && S1[0].id >= rp + 1) {
int nxt = S1.back().id;
while((int)S1.size() > 0) {
S1.pop_back();
}
for(int i = nxt; i < last; ++i) {
if((int)S2.size() >= 1 && S2.back().x == lines[i].x) continue;
while((int)S2.size() >= 2 && intersect(S2.back(), lines[i], S2[(int)S2.size() - 2]) >= 0) {
rem[i].PB(S2.back().id);
S2.pop_back();
}
S2.PB(lines[i]);
}
last = nxt;
ptr = 0;
}
while(S2.size() > 0 && S2.back().id >= rp + 1) {
if(ptr > 0) ptr--;
reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
int id = S2.back().id;
S2.pop_back();
for(int x : rem[id]) {
S2.PB(lines[x]);
}
// must add points
}
ll w1 = get_mx(S1, -lp + 1);
ll w2 = get_mx2(-lp + 1);
//cerr << lp << " " << r2 << " " << rp << " " << max(w1, w2) * f[lp] << "\n";
ans = max(ans, max(w1,w2) * f[lp]);
}
}
// ---------------------------
lp = l;
l2 = l;
lines[mid] = {(ll)g[mid], (ll)g[mid] * (-mid + 1), mid};
S1.clear(); S2.clear();
S1.PB(lines[l]);
ptr = 0;
last = l - 1;
for(int i = l; i <= mid; ++i) rem[i].clear();
for(rp = r; rp >= mid; rp--) {
while(l2 + 1 <= mid && (g[rp] >= g[l2 + 1])) {
l2++;
if((int)S1.size() >= 1 && S1.back().x == lines[l2].x) continue;
while((int)S1.size() >= 2 && intersect(S1.back(), lines[l2], S1[(int)S1.size() - 2]) <= 0) {
S1.pop_back();
}
S1.PB(lines[l2]);
// add
}
while(lp <= mid && (f[rp] > f[lp])) {
lp++;
}
if(lp <= mid && g[rp] >= g[l2] && lp <= l2) {
// [r2, rp]
// ans = max(ans, ask(lp, l2, rp) * f[rp]);
while(S2.size() > 0 && S2.back().id <= lp - 1) {
if(ptr > 0) ptr--;
reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
int id = S2.back().id;
S2.pop_back();
for(int x : rem[id]) {
S2.PB(lines[x]);
}
// must add points
}
if((int)S1.size() > 0 && S1[0].id <= lp - 1) {
int nxt = S1.back().id;
while((int)S1.size() > 0) {
S1.pop_back();
}
for(int i = nxt; i > last; --i) {
if((int)S2.size() >= 1 && S2.back().x == lines[i].x) continue;
while((int)S2.size() >= 2 && intersect(S2.back(), lines[i], S2[(int)S2.size() - 2]) >= 0) {
rem[i].PB(S2.back().id);
S2.pop_back();
}
S2.PB(lines[i]);
}
last = nxt;
ptr = 0;
}
while(S2.size() > 0 && S2.back().id <= lp - 1) {
if(ptr > 0) ptr--;
reverse(rem[S2.back().id].begin(), rem[S2.back().id].end());
int id = S2.back().id;
S2.pop_back();
for(int x : rem[id]) {
S2.PB(lines[x]);
}
// must add points
}
ll w1 = get_mx(S1, rp);
ll w2 = get_mx2(rp);
//if(mid == 1) {
//cerr << rp << ":\n";
//for(auto x : S1) {
//cerr << x.x << " " << x.y << " " << x.id << "\n";
//}
//cerr << "---\n";
//for(auto x : S2) {
//cerr << x.x << " " << x.y << " " << x.id << "\n";
//}
//cerr << "---\n";
//}
ans = max(ans, max(w1,w2) * f[rp]);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
rec(0, n - 1);
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5128 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5068 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5128 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5068 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5068 KB |
Output is correct |
| 13 |
Correct |
150 ms |
13456 KB |
Output is correct |
| 14 |
Correct |
158 ms |
15248 KB |
Output is correct |
| 15 |
Correct |
118 ms |
13240 KB |
Output is correct |
| 16 |
Correct |
116 ms |
13280 KB |
Output is correct |
| 17 |
Correct |
128 ms |
14496 KB |
Output is correct |
| 18 |
Correct |
123 ms |
14640 KB |
Output is correct |
| 19 |
Correct |
128 ms |
14164 KB |
Output is correct |
| 20 |
Correct |
140 ms |
15184 KB |
Output is correct |
| 21 |
Correct |
137 ms |
13248 KB |
Output is correct |
| 22 |
Correct |
150 ms |
14536 KB |
Output is correct |
| 23 |
Correct |
16 ms |
5840 KB |
Output is correct |
| 24 |
Correct |
129 ms |
12820 KB |
Output is correct |
