#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define N 200051
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
//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;
int n, a[N], b[N], pr[N][2], sf[N][2];
vector <pair <ll, ll> > t[N * 4];
ll ans = 0;
ll inter(pair <ll, ll> x, pair <ll, ll> y)
{
ll a = (x.F - y.F);
ll b = (y.S - x.S);
if (a == 0)
{
if (a >= 0)
return 1e18;
return -1e18;
}
bool f1 = (a <= 0);
bool f2 = (b <= 0);
if (f1 && f2)
return b / a + bool(b % a);
return b / a;
}
void bld(int v, int tl, int tr)
{
t[v].clear();
int ps = tl;
while (ps < tr && pr[ps + 1][0] == pr[tl][0])
ps++;
t[v].PB({-pr[ps][0], 1ll * pr[ps][0] * ps});
for (int i = ps + 1; i <= tr; i++)
{
pair <ll, ll> pt = {-pr[i][0], 1ll * pr[i][0] * i};
while(sz(t[v]) > 1)
{
pair <ll, ll> lst = t[v][sz(t[v]) - 2];
ll a = inter(lst, t[v].back());
ll b = inter(t[v].back(), pt);
if (b > a)
break;
t[v].pop_back();
}
t[v].PB(pt);
}
if (tl == tr) return;
int md = (tl + tr) >> 1;
bld(v + v, tl, md);
bld(v + v + 1, md + 1, tr);
}
ll get(int v, int tl, int tr, int l, int r, ll x)
{
if (tr < l || l > r || r < tl || tl > tr) return 0;
if (l <= tl && tr <= r)
{
while (sz(t[v]) > 1 && inter(t[v].back(), t[v][sz(t[v]) - 1]) > x)
t[v].pop_back();
return t[v].back().S + t[v].back().F * x;
}
int md = (tl + tr) >> 1;
return max(get(v + v, tl, md, l, r, x), get(v + v + 1, md + 1, tr, l, r, x));
}
void calc(int l, int r)
{
for (int i = l; i <= r; i++)
swap(a[i], b[i]);
int md = (l + r) >> 1;
sf[md][0] = a[md];
sf[md][1] = b[md];
for (int i = md - 1; i >= l; i--)
{
sf[i][0] = min(sf[i + 1][0], a[i]);
sf[i][1] = min(sf[i + 1][1], b[i]);
}
pr[md + 1][0] = a[md + 1];
pr[md + 1][1] = b[md + 1];
for (int i = md + 2; i <= r; i++)
{
pr[i][0] = min(pr[i - 1][0], a[i]);
pr[i][1] = min(pr[i - 1][1], b[i]);
}
bld(1, md + 1, r);
int i1 = r;
int i2 = md + 1;
for (int i = md; i >= l; i--)
{
while (i1 >= md + 1 && pr[i1][0] > sf[i][0])
i1--;
while (i2 <= r && pr[i2][1] < sf[i][1])
i2++;
if (i2 <= r && i1 >= md + 1 && i1 <= i2)
ans = max(ans, get(1, md + 1, r, i1, i2, i - 1) * sf[i][1]);
}
}
void solve(int l, int r)
{
if (l == r)
{
ans = max(ans, 1ll * a[l] * b[l]);
return;
}
int md = (l + r) >> 1;
solve(l, md);
solve(md + 1, r);
sf[md][0] = a[md];
sf[md][1] = b[md];
for (int i = md - 1; i >= l; i--)
{
sf[i][0] = min(sf[i + 1][0], a[i]);
sf[i][1] = min(sf[i + 1][1], b[i]);
}
pr[md + 1][0] = a[md + 1];
pr[md + 1][1] = b[md + 1];
for (int i = md + 2; i <= r; i++)
{
pr[i][0] = min(pr[i - 1][0], a[i]);
pr[i][1] = min(pr[i - 1][1], b[i]);
}
int j = r;
for (int i = md; i >= l; i--)
{
while (j >= md + 1 && (sf[i][0] > pr[j][0] || sf[i][1] > pr[j][1]))
j--;
if (j >= md + 1)
ans = max(ans, 1ll * (j - i + 1) * sf[i][0] * sf[i][1]);
}
j = l;
for (int i = md + 1; i <= r; i++)
{
while (j <= md && (pr[i][0] > sf[j][0] || pr[i][1] > sf[j][1]))
j++;
if (j <= md)
ans = max(ans, 1ll * (i - j + 1) * pr[i][0] * pr[i][1]);
}
calc(l, r);
calc(l, r);
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
solve(1, n);
pri(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
