#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <ll, ll>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;
const int N = 2e5 + 500;
const int MS = 1e6;
int sfa[N], sfb[N], pra[N], prb[N], a[N], b[N];
ll ans;
int n;
int root[4 * N];
ll lst[MS], cr[MS];
pair <ll, ll> ln[MS];
int siz;
int add(ll k, ll b) {
int v = siz++;
ln[v] = {k, b};
return siz - 1;
}
ll cross(ll k, ll b, ll k1, ll b1) {
return ((b - b1) / (k1 - k) + !!((b - b1) % (k1 - k)));
}
void build(int v, int l, int r) {
int i = l;
while (i <= r && prb[l] == prb[i])
i++;
root[v] = add(-prb[i - 1], prb[i - 1] * i);
lst[root[v]] = root[v];
cr[root[v]] = -1e18;
int last = root[v];
for (; i <= r;) {
int j = i;
while (i <= r && prb[i] == prb[j])
i++;
ll k = -prb[i - 1], b = prb[i - 1] * i;
ll crp;
while (1) {
crp = cross(k, b, ln[last].F, ln[last].S);
if (crp > cr[last])
break;
last = lst[last];
}
root[v] = add(k, b);
lst[root[v]] = last;
cr[root[v]] = crp;
last = root[v];
}
if (l == r)
return;
int md = (l + r) >> 1;
build(v * 2, l, md);
build(v * 2 + 1, md + 1, r);
}
void upd_a(ll vl) {
ans = max(ans, vl);
}
ll get(int v, int l, int r, int tl, int tr, int X) {
if (l > r || tl > tr || tl > r || l > tr)
return -1e18;
if (l == tl && r == tr) {
while (cr[root[v]] > X)
root[v] = lst[root[v]];
return ln[root[v]].F * X + ln[root[v]].S;
}
int md = (l + r) >> 1;
return max(get(v * 2, l, md, tl, min(md, tr), X),
get(v * 2 + 1, md + 1, r, max(md + 1, tl), tr, X));
}
void solve(int le, int ri) {
if (le > ri)
return;
if (le == ri) {
upd_a(a[le] * b[le]);
return;
}
int md = (le + ri) >> 1;
/// f -> [le, md], g -> [le, md]
pra[md] = prb[md] = 1e9;
for (int i = md + 1; i <= ri; i++) {
pra[i] = min(pra[i - 1], a[i]);
prb[i] = min(prb[i - 1], b[i]);
}
int r = md + 1, f = 1e9, g = 1e9;
for (int l = md; l >= le; l--) {
f = min(f, a[l]);
g = min(g, b[l]);
while (r <= ri && pra[r] >= f && prb[r] >= g)
r++;
upd_a((r - l) * 1ll * f * g);
}
///f -> [md, ri], g -> [md; ri]
sfa[md] = sfb[md] = 1e9;
for (int l = md - 1; l >= le; l--) {
sfa[l] = min(sfa[l + 1], a[l]);
sfb[l] = min(sfb[l + 1], b[l]);
}
int l = md - 1;
f = 1e9, g = 1e9;
for (int r = md; r <= ri; r++) {
f = min(f, a[r]);
g = min(g, b[r]);
while (l >= le && sfa[l] >= f && sfb[l] >= g)
l--;
upd_a((r - l) * 1ll * f * g);
}
/// f -> [le, md], g -> [md + 1, ri]
siz = 0;
build(1, md + 1, ri);
f = 1e9, g = 1e9;
r = md + 1;
int r1 = md + 1;
for (int l = md; l >= le; l--) {
f = min(f, a[l]);
g = min(g, b[l]);
while (r <= ri && g < prb[r])
r++;
while (r1 <= ri && f <= pra[r1])
r1++;
if (r <= r1 - 1) {
ll cur = get(1, md + 1, ri, r, r1 - 1, l);
// cerr << f * cur << el;
if (cur != -1e18) {
upd_a(f * cur);
}
}
}
/// g -> [le, md], f -> [md + 1, ri]
siz = 0;
for (int i = md + 1; i <= ri; i++) {
swap(pra[i], prb[i]);
}
build(1, md + 1, ri);
f = 1e9, g = 1e9;
r = md + 1;
r1 = md + 1;
for (int l = md; l >= le; l--) {
f = min(f, a[l]);
g = min(g, b[l]);
while (r <= ri && g <= pra[r])
r++;
while (r1 <= ri && f < prb[r1])
r1++;
if (r1 <= r - 1) {
ll cur = get(1, md + 1, ri, r1, r - 1, l);
if (cur != -1e18) {
upd_a(g * cur);
}
}
}
//806801766313992
//1675888823757
solve(le, md - 1);
solve(md + 1, ri);
}
int main()
{
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("game.in");
// out("game.out");
// in("input.txt");
// out("output.txt");
// clock_t tStart = clock();
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
solve(1, n);
cout << ans;
}
/*
7
4 6 7 2 3 1 5
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
2 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
2 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
2 ms |
460 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
2 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
2 ms |
460 KB |
Output is correct |
| 13 |
Incorrect |
278 ms |
12540 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
