// Cast your cares on the Lord and he will sustain you;
// he will never let the righteous be shaken
// Psalms 55:22
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005
int n;
int a[MAXN], b[MAXN];
struct line {
ll m, c;
ll isect(const line &o) const {
return (c - o.c) / (o.m - m);
}
ll eval(ll x) {
return m * x + c;
}
};
struct event {
line l;
int s, e;
};
ll ans;
int pfa[MAXN], pfb[MAXN];
int st[MAXN];
deque<line> dq;
void insert(line l) {
if (!dq.empty() && dq.back().m == l.m) {
if (dq.back().c <= l.c) {
dq.pop_back();
} else {
return;
}
}
while (dq.size() >= 2 && l.isect(dq[dq.size() - 1]) <=
dq[dq.size() - 1].isect(dq[dq.size() - 2])) {
dq.pop_back();
}
dq.pb(l);
}
void dnct(int s, int e, vector<event> &ev) {
if (ev.empty()) return;
int m = s + e >> 1;
vector<event> lev, rev;
for (auto ce : ev) {
if (ce.s <= s && ce.e >= e) {
insert(ce.l);
} else {
if (ce.s <= m) {
lev.pb(ce);
}
if (ce.e > m) {
rev.pb(ce);
}
}
}
if (!dq.empty()) {
REP (i, s, e + 1) {
while (dq.size() >= 2 && dq[0].eval(i) <= dq[1].eval(i)) {
dq.pop_front();
}
mxto(ans, (ll) pfa[i] * dq[0].eval(i));
}
}
dnct(s, m, lev); dnct(m + 1, e, rev);
}
void dnc(int s, int e) {
if (s == e) {
mxto(ans, (ll) a[s] * b[s]);
return;
}
assert(s < e);
int m = s + e >> 1;
REP (i, m + 1, e + 1) {
pfa[i] = a[i];
if (i != m + 1) {
mnto(pfa[i], pfa[i - 1]);
}
pfb[i] = b[i];
if (i != m + 1) {
mnto(pfb[i], pfb[i - 1]);
}
}
RREP (i, m, s) {
pfa[i] = a[i];
if (i != m) {
mnto(pfa[i], pfa[i + 1]);
}
pfb[i] = b[i];
if (i != m) {
mnto(pfb[i], pfb[i + 1]);
}
}
// a and b minimum on left
int ptr = m;
RREP (i, m, s) {
while (ptr + 1 <= e &&
pfa[i] <= pfa[ptr + 1] && pfb[i] <= pfb[ptr + 1]) {
ptr++;
}
if (ptr > m) {
mnto(ans, (ll) pfa[i] * pfb[i] * (ptr - i + 1));
}
}
// a minimum on left, b minimum on right
vector<event> ev;
int l = m + 1, r = m;
RREP (i, m, s) {
while (r + 1 <= e && pfa[i] <= pfa[r + 1]) {
r++;
st[r] = i;
}
while (l <= r && pfb[i] < pfb[l]) {
if (st[l] != i) {
line tmp = {-pfb[l], (ll) (l + 1) * pfb[l]};
ev.pb({tmp, i + 1, st[l]});
}
l++;
}
}
while (l <= r) {
// en = i - 1
line tmp = {-pfb[l], (ll) (l + 1) * pfb[l]};
ev.pb({tmp, s, st[l]});
l++;
}
dnct(s, m, ev);
dnc(s, m); dnc(m + 1, e);
}
int main() {
scanf("%d", &n);
REP (i, 0, n) {
scanf("%d%d", &a[i], &b[i]);
}
REP (_, 0, 2) {
dnc(0, n - 1);
reverse(a, a + n);
reverse(b, b + n);
}
printf("%lld\n", ans);
return 0;
}
Compilation message
histogram.cpp: In function 'void dnct(int, int, std::vector<event>&)':
histogram.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int m = s + e >> 1;
| ~~^~~
histogram.cpp: In function 'void dnc(int, int)':
histogram.cpp:107:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
107 | int m = s + e >> 1;
| ~~^~~
histogram.cpp: In function 'int main()':
histogram.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
histogram.cpp:168:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
168 | scanf("%d%d", &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
924 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
924 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
