// 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) {
return;
}
dq.pop_back();
}
assert(dq.empty() || dq.back().m < l.m);
while (dq.size() >= 2 && l.isect(dq[dq.size() - 1]) <=
l.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;
dq.clear();
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);
}
int zz;
void dnc(int s, int e) {
if (s == e) {
mxto(ans, (ll) a[s] * b[s]);
return;
}
assert(s < e);
int m = s + e + zz>> 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++;
}
mxto(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) {
line tmp = {-pfb[l], (ll) (l + 1) * pfb[l]};
ev.pb({tmp, s, st[l]});
l++;
}
dnct(s, m, ev);
dnc(s, m - zz); dnc(m + 1 - zz, e);
}
int main() {
scanf("%d", &n);
REP (i, 0, n) {
scanf("%d%d", &a[i], &b[i]);
}
dnc(0, n - 1);
reverse(a, a + n);
reverse(b, b + n);
zz = 1;
dnc(0, n - 1);
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:109:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int m = s + e + zz>> 1;
| ~~~~~~^~~~
histogram.cpp: In function 'int main()':
histogram.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
histogram.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d%d", &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
676 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
844 KB |
Output is correct |
| 4 |
Correct |
3 ms |
664 KB |
Output is correct |
| 5 |
Correct |
2 ms |
688 KB |
Output is correct |
| 6 |
Correct |
3 ms |
716 KB |
Output is correct |
| 7 |
Correct |
2 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
636 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1012 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1052 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
3 ms |
928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
676 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
844 KB |
Output is correct |
| 4 |
Correct |
3 ms |
664 KB |
Output is correct |
| 5 |
Correct |
2 ms |
688 KB |
Output is correct |
| 6 |
Correct |
3 ms |
716 KB |
Output is correct |
| 7 |
Correct |
2 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
636 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1012 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1052 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
3 ms |
928 KB |
Output is correct |
| 13 |
Correct |
617 ms |
110868 KB |
Output is correct |
| 14 |
Correct |
228 ms |
43468 KB |
Output is correct |
| 15 |
Correct |
558 ms |
96968 KB |
Output is correct |
| 16 |
Correct |
664 ms |
120580 KB |
Output is correct |
| 17 |
Correct |
541 ms |
60948 KB |
Output is correct |
| 18 |
Correct |
502 ms |
76020 KB |
Output is correct |
| 19 |
Correct |
453 ms |
69956 KB |
Output is correct |
| 20 |
Correct |
552 ms |
83472 KB |
Output is correct |
| 21 |
Correct |
700 ms |
120424 KB |
Output is correct |
| 22 |
Correct |
584 ms |
122100 KB |
Output is correct |
| 23 |
Correct |
40 ms |
5720 KB |
Output is correct |
| 24 |
Correct |
355 ms |
12872 KB |
Output is correct |
