#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
#define taskname "Histogram"
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> point;
const int N = 2e5 + 1;
point operator - (const point &a, const point &b){
return point(a.X - b.X, a.Y - b.Y);
}
ll operator * (const point &a, const point &b){
return a.X * b.Y - a.Y * b.X;
}
bool CW(point &a, point &b, point &c){
return (b - a) * (c - b) < 0;
}
struct convexHull{
vector <point> d;
int ptr = -1;
void reset(){
d.clear();
}
void add(point p){
d.push_back(p);
}
void findConvexHull(){
vector <point> res;
for(point p : d){
while (res.size() > 1){
if (!CW(res[res.size() - 2], res[res.size() - 1], p))
res.pop_back();
else
break;
}
res.push_back(p);
}
swap(res, d);
ptr = d.size() - 1;
}
ll findMax(point a){
if (d.empty())
return 0;
while (ptr > 0 && a * d[ptr] < a * d[ptr - 1])
ptr--;
return a * d[ptr];
}
} cvh;
struct segmentTree{
convexHull d[N * 2];
void reset(int id, int l, int r){
d[id].reset();
if (l == r)
return;
int mid = (l + r) >> 1;
reset(id << 1, l, mid);
reset(id << 1 | 1, mid + 1, r);
}
void add(int id, int l, int r, int pos, point p){
if (pos < l || r < pos)
return;
d[id].add(p);
if (l == r)
return;
int mid = (l + r) >> 1;
add(id << 1, l, mid, pos, p);
add(id << 1 | 1, mid + 1, r, pos, p);
}
void findConvexHull(int id, int l, int r){
d[id].findConvexHull();
if (l == r)
return;
int mid = (l + r) >> 1;
findConvexHull(id << 1, l, mid);
findConvexHull(id << 1 | 1, mid + 1, r);
}
ll getMax(int id, int l, int r, int u, int v, point p){
if (v < l || r < u || u > v)
return 0;
if (u <= l && r <= v)
return d[id].findMax(p);
int mid = (l + r) >> 1;
return max(getMax(id << 1, l, mid, u, v, p), getMax(id << 1 | 1, mid + 1, r, u, v, p));
}
} ST;
int n, a[N], b[N];
int minA[N], minB[N], x[N], y[N];
void readInput(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
}
ll calc(int l, int r, int d){
if (l > r)
return 0;
int mid = (l + r + d) >> 1;
minA[mid] = a[mid];
minB[mid] = b[mid];
for(int i = mid + 1; i <= r; i++){
minA[i] = min(minA[i - 1], a[i]);
minB[i] = min(minB[i - 1], b[i]);
}
for(int i = mid - 1; i >= l; i--){
minA[i] = min(minA[i + 1], a[i]);
minB[i] = min(minB[i + 1], b[i]);
}
ll res = 0;
int ptr;
/// minA and minB in left
ptr = mid;
for(int cur = mid; cur >= l; cur--){
while (ptr <= r && minA[cur] <= minA[ptr] && minB[cur] <= minB[ptr])
ptr++;
res = max(res, (ll) (ptr - cur) * minA[cur] * minB[cur]);
}
/// minA in left and minB in right
ptr = mid;
for(int cur = mid; cur >= l; cur--){
while (ptr <= r && minA[cur] <= minA[ptr])
ptr++;
y[cur] = ptr - 1;
}
ptr = mid;
for(int cur = mid; cur >= l; cur--){
while (ptr <= r && minB[cur] < minB[ptr])
ptr++;
x[cur] = ptr;
}
ST.reset(1, mid, r);
for(int j = r; j >= mid; j--)
ST.add(1, mid, r, j, point(minB[j], (ll) minB[j] * j));
ST.findConvexHull(1, mid, r);
for(int i = l; i <= mid; i++)
res = max(res, ST.getMax(1, mid, r, x[i], y[i], point(minA[i], (ll) minA[i] * (i - 1))));
res = max(res, calc(l, mid - 1, d));
res = max(res, calc(mid + 1, r, d));
return res;
}
void solve(){
ll res = 0;
res = max(res, calc(1, n, 0));
reverse(a + 1, a + 1 + n);
reverse(b + 1, b + 1 + n);
res = max(res, calc(1, n, 1));
cout << res;
}
int main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
readInput();
solve();
return 0;
}
Compilation message
histogram.cpp: In function 'int main()':
histogram.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
172 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
13132 KB |
Output is correct |
| 2 |
Correct |
13 ms |
13132 KB |
Output is correct |
| 3 |
Correct |
14 ms |
13108 KB |
Output is correct |
| 4 |
Correct |
14 ms |
13132 KB |
Output is correct |
| 5 |
Correct |
12 ms |
13132 KB |
Output is correct |
| 6 |
Correct |
16 ms |
13136 KB |
Output is correct |
| 7 |
Correct |
13 ms |
13132 KB |
Output is correct |
| 8 |
Correct |
13 ms |
13136 KB |
Output is correct |
| 9 |
Correct |
15 ms |
13120 KB |
Output is correct |
| 10 |
Correct |
13 ms |
13132 KB |
Output is correct |
| 11 |
Correct |
7 ms |
12876 KB |
Output is correct |
| 12 |
Correct |
14 ms |
13140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
13132 KB |
Output is correct |
| 2 |
Correct |
13 ms |
13132 KB |
Output is correct |
| 3 |
Correct |
14 ms |
13108 KB |
Output is correct |
| 4 |
Correct |
14 ms |
13132 KB |
Output is correct |
| 5 |
Correct |
12 ms |
13132 KB |
Output is correct |
| 6 |
Correct |
16 ms |
13136 KB |
Output is correct |
| 7 |
Correct |
13 ms |
13132 KB |
Output is correct |
| 8 |
Correct |
13 ms |
13136 KB |
Output is correct |
| 9 |
Correct |
15 ms |
13120 KB |
Output is correct |
| 10 |
Correct |
13 ms |
13132 KB |
Output is correct |
| 11 |
Correct |
7 ms |
12876 KB |
Output is correct |
| 12 |
Correct |
14 ms |
13140 KB |
Output is correct |
| 13 |
Correct |
1935 ms |
56568 KB |
Output is correct |
| 14 |
Correct |
1980 ms |
56504 KB |
Output is correct |
| 15 |
Correct |
2231 ms |
56260 KB |
Output is correct |
| 16 |
Correct |
2103 ms |
56448 KB |
Output is correct |
| 17 |
Correct |
1987 ms |
56596 KB |
Output is correct |
| 18 |
Correct |
1873 ms |
56352 KB |
Output is correct |
| 19 |
Correct |
1934 ms |
56448 KB |
Output is correct |
| 20 |
Correct |
1942 ms |
56572 KB |
Output is correct |
| 21 |
Correct |
1910 ms |
56652 KB |
Output is correct |
| 22 |
Correct |
2033 ms |
56428 KB |
Output is correct |
| 23 |
Correct |
132 ms |
17092 KB |
Output is correct |
| 24 |
Correct |
2025 ms |
56540 KB |
Output is correct |
