#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];
pair<ll, ll> lines[nax];
ll ans;
vector<pair<ll, ll>>T[(1 << 19)];
int R;
long double intersect(pair<ll,ll>&x, pair<ll,ll>&y) {
return (long double)(y.ND - x.ND) / (x.ST - y.ST);
}
void construct(int l, int r) {
for(int i = l; i <= r; ++i) {
T[i + R].resize(1);
T[i + R][0] = lines[i];
}
//cerr << "OK\n";
l += R; r += R;
int memol = l, memor = r;
while(l/2 > 0) {
l /= 2; r /= 2;
for(int i = l; i <= r; ++i) {
int v = i;
T[v].clear();
//cerr << i << "\n";
for(auto x : T[2*v+1]) {
T[v].PB(x);
}
for(auto x : T[2*v]) {
T[v].PB(x);
}
}
}
//cerr << "W\n";
l = memol; r = memor;
while(l/2 > 0) {
l /= 2; r /= 2;
for(int i = l; i <= r; ++i) {
int v = i;
vector<pair<ll,ll>>nw = {};
for(auto x : T[v]) {
if((int)nw.size() == 0) {
nw.PB(x);
continue;
}
if(nw.back().ST == x.ST) continue;
while((int)nw.size() >= 2 && intersect(nw.back(), x) <= intersect(nw.back(), nw[(int)nw.size() - 2])) {
nw.pop_back();
}
nw.PB(x);
}
T[v].swap(nw);
}
}
//cerr << "WTF\n";
}
ll get_mx(vector<pair<ll,ll>>&vec, int x) {
while((int)vec.size() >= 2 && vec.back().ST * x + vec.back().ND <= vec[(int)vec.size() - 2].ST * x + vec[(int)vec.size() - 2].ND) {
vec.pop_back();
}
return vec.back().ST * x + vec.back().ND;
}
ll ask(int l, int r, int x) {
l += R; r += R;
ll w = max(get_mx(T[l], x), get_mx(T[r], x));
while(l /2 != r/2) {
if(l % 2 == 0) w = max(w, get_mx(T[l + 1], x));
if(r % 2 == 1) w = max(w, get_mx(T[r - 1], x));
l /= 2;
r /= 2;
}
return w;
}
void rec(int l, int r) {
int mid = (l + r) / 2;
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};
for(int i = mid - 1; i >= l; --i) {
f[i] = min(f[i + 1], a[i]);
g[i] = min(g[i + 1], b[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};
}
//cerr << mid << " " << r << " " << R << "\n";
construct(mid, r);
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;
for(lp = l; lp <= mid; lp++) {
while(rp >= mid && (f[lp] > f[rp])) {
rp--;
// erase
}
while(r2 - 1 >= mid && (g[lp] >= g[r2 - 1])) {
r2--;
// add
}
if(rp >= mid && g[lp] >= g[r2] && r2 <= rp) {
// [r2, rp]
//for(int i = 1; i < 2 * R; ++i) {
//cout << i << ": ";
//for(auto x : T[i]) cout << "(" << x.ST << " " << x.ND << ") ";
//cout << "\n";
//}
//cerr << lp << " " << r2 << " " << rp << "\n";
ans = max(ans, ask(r2, rp, -lp + 1) * f[lp]);
//cout << "ASK\n";
//for(r2 = rp; r2 >= mid; r2--) {
//if(g[lp] < g[r2]) break;
//ans = max(ans, (ll)f[lp] * g[r2] * (r2 - lp + 1));
//}
}
}
//for(int i = 1; i < 2 * R; ++i) T[i].clear();
lp = l;
for(rp = r; rp >= mid; rp--) {
while(lp <= mid && (f[rp] > f[lp])) {
lp++;
}
if(lp <= mid) {
for(l2 = lp; l2 <= mid; l2++) {
if(g[rp] < g[l2]) break;
ans = max(ans, (ll)f[rp] * g[l2] * (rp - l2 + 1));
}
}
}
}
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];
}
R = 1;
while(R < n) R *= 2;
rec(0, n - 1);
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
13004 KB |
Output is correct |
| 2 |
Correct |
16 ms |
13024 KB |
Output is correct |
| 3 |
Correct |
15 ms |
13004 KB |
Output is correct |
| 4 |
Correct |
16 ms |
13028 KB |
Output is correct |
| 5 |
Correct |
16 ms |
13004 KB |
Output is correct |
| 6 |
Correct |
17 ms |
13004 KB |
Output is correct |
| 7 |
Correct |
15 ms |
12980 KB |
Output is correct |
| 8 |
Correct |
23 ms |
12940 KB |
Output is correct |
| 9 |
Correct |
25 ms |
13004 KB |
Output is correct |
| 10 |
Correct |
17 ms |
13004 KB |
Output is correct |
| 11 |
Correct |
6 ms |
12620 KB |
Output is correct |
| 12 |
Correct |
16 ms |
13020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
13004 KB |
Output is correct |
| 2 |
Correct |
16 ms |
13024 KB |
Output is correct |
| 3 |
Correct |
15 ms |
13004 KB |
Output is correct |
| 4 |
Correct |
16 ms |
13028 KB |
Output is correct |
| 5 |
Correct |
16 ms |
13004 KB |
Output is correct |
| 6 |
Correct |
17 ms |
13004 KB |
Output is correct |
| 7 |
Correct |
15 ms |
12980 KB |
Output is correct |
| 8 |
Correct |
23 ms |
12940 KB |
Output is correct |
| 9 |
Correct |
25 ms |
13004 KB |
Output is correct |
| 10 |
Correct |
17 ms |
13004 KB |
Output is correct |
| 11 |
Correct |
6 ms |
12620 KB |
Output is correct |
| 12 |
Correct |
16 ms |
13020 KB |
Output is correct |
| 13 |
Execution timed out |
2575 ms |
38604 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
