#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
void add(int &a, const int b) {if((a += b) >= md) a -= md;}
void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
int prod(const int a, const int b) {return ll(a) * b % md;}
};
int n;
const int N = 2e5 + 5;
int a[N], b[N];
pii l[N], r[N];
ll ans;
inline void upd(ll a, ll b, ll c) {umax(ans, a * b * c);}
struct line {
int a;
ll b;
int i, x;
int X(const line &f) const {
ll t = f.b - b;
ll u = a - f.a;
ll z = (t < 0 ? t - u + 1 : t) / u;
return z > n ? n : z < 1 ? 1 : z;
}
};
deque<line> f;
int opt;
void add(pii &t, int i) {
int a = t.sd;
ll b = (ll)t.sd * (i + 1);
line p{a, b, i, n};
for(;;) {
if(f.empty()) {
f.push_back(p);
return;
}
line &li = f.back();
if(li.a == a) {
li.i = i;
return;
}
int x = li.X(p);
if(x < li.x) {
p.x = x;
f.push_back(p);
return;
}
f.pop_back();
if(opt == len(f)) --opt;
}
}
void del(int i) {
for(; !f.empty() && f.front().i <= i; f.pop_front())
if(opt > 0) --opt;
}
void calc(pii *l, int n, pii *r, int m) {
f.clear();
int fi{}, se{};
opt = 0;
for(int i = 0; i < n; ++i) {
while(fi < m && r[fi].ft >= l[i].ft) add(r[fi], fi), ++fi;
while(se < fi && r[se].sd >= l[i].sd) del(se++);
upd(l[i].ft, l[i].sd, se + i + 1);
while(opt + 1 < len(f) && f[opt + 1].x >= i + 1) ++opt;
if(opt < len(f)) umax(ans, l[i].ft * (f[opt].b + f[opt].a * ll(i + 1)));
}
}
void calc(int L, int R) {
int MD = L + R >> 1;
if(L < MD) calc(L, MD - 1);
if(MD + 1 < R) calc(MD + 1, R);
int A = +inf, B = +inf, n = 0, m = 0;
for(int i = MD; i >= L; --i) {
umin(A, a[i]);
umin(B, b[i]);
l[n++] = {A, B};
}
A = +inf, B = +inf;
for(int i = MD + 1; i <= R; ++i) {
umin(A, a[i]);
umin(B, b[i]);
r[m++] = {A, B};
}
calc(l, n, r, m);
calc(r, m, l, n);
}
void solve() {
cin >> n;
ans = 0;
for(int i = 0; i < n; ++i)
cin >> a[i] >> b[i],
upd(a[i], b[i], 1);
calc(0, n - 1);
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
#else
system("color a");
freopen("in.txt", "r", stdin);
int t; cin >> t;
while(t--)
#endif
solve();
}
Compilation message
histogram.cpp: In function 'void calc(int, int)':
histogram.cpp:96:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int MD = L + R >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
360 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
360 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
