// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
int n;
ll h[200001], w[200001];
bool print = 0;
struct Node {
int lo, hi;
vpll points, hull;
Node *l, *r;
Node(const vector<pair<ll, pll>> &vec, int L, int R) : lo(L), hi(R) {
if (hi - lo == 1) {
points.emplace_back(vec[lo].second);
hull.pb(points[0]);
} else {
int mid = (hi + lo) / 2;
l = new Node(vec, lo, mid);
r = new Node(vec, mid, hi);
points = l->points;
trav(point, r->points) points.emplace_back(point);
hull.emplace_back(points[0]);
hull.emplace_back(points[1]);
rep(i, 2, sz(points)) {
pll cur = points[i];
pll prev = hull.back();
pll pprev = hull[sz(hull) - 2];
while (slope(pprev, prev) < slope(pprev, cur)) {
hull.pop_back();
if (sz(hull) == 1) break;
prev = hull.back();
pprev = hull[sz(hull) - 2];
}
hull.push_back(cur);
}
}
}
double slope(pll p1, pll p2) { return double(p2.second - p1.second) / double(p2.first - p1.first); }
ll query(int L, int R, pll point) {
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) {
ll ans = 0;
int cur_lo = 0, cur_hi = sz(hull) - 1;
while (cur_hi - cur_lo >= 3) {
int m1 = cur_lo + (cur_hi - cur_lo) / 3, m2 = cur_hi - (cur_hi - cur_lo) / 3;
ll ans1 = volume(point, hull[m1]);
ll ans2 = volume(point, hull[m2]);
if (ans1 > ans2)
cur_hi = m2;
else
cur_lo = m1;
}
rep(i, cur_lo, cur_hi + 1) ans = max(ans, volume(point, hull[i]));
return ans;
}
return max(l->query(L, R, point), r->query(L, R, point));
}
ll volume(pll p1, pll p2) { return p1.first * p2.first + p1.second * p2.second; }
};
ll solve(int lo, int hi) {
if (hi < lo) return 0;
if (lo == hi) return h[lo] * w[hi];
int mid = (lo + hi) / 2;
ll ansL = solve(lo, mid - 1), ansR = solve(mid + 1, hi);
ll ans = max(ansL, ansR);
rep(_, 0, 2) {
int j = mid + 1;
ll curh = h[mid], curw = w[mid];
per(i, lo, mid + 1) {
curh = min(curh, h[i]);
curw = min(curw, w[i]);
while (j <= hi && curh <= h[j] && curw <= w[j]) ++j;
ans = max(ans, curh * curw * (j - i));
}
curw = INF;
vector<pair<ll, pll>> points;
if (hi - lo == 5) print = 1;
rep(i, mid, hi + 1) {
curw = min(curw, w[i]);
points.pb({-i, {curw, curw * i}});
}
sort(all(points));
Node segtree(points, 0, sz(points));
curh = h[mid], curw = w[mid];
int start = mid, stop = mid;
per(i, lo, mid + 1) {
curh = min(curh, h[i]);
curw = min(curw, w[i]);
while (stop <= hi && curh <= h[stop]) ++stop;
while (start <= hi && curw < w[start]) ++start;
if (start < stop) {
ans = max(ans, segtree.query((hi - stop + 1) - mid, (hi - start + 1) - mid, {curh * (1 - i), curh}));
}
}
reverse(h + lo, h + hi + 1);
reverse(w + lo, w + hi + 1);
}
//cout << "lo = " << lo << " hi = " << hi << endl;
//cout << "ans = " << ans << endl
// << endl;
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n;
rep(i, 0, n) cin >> h[i] >> w[i];
ll ans = solve(0, n - 1);
cout<<ans<<endl;
return 0;
}
Compilation message
histogram.cpp: In constructor 'Node::Node(const std::vector<std::pair<long long int, std::pair<long long int, long long int> > >&, int, int)':
histogram.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
| ^
histogram.cpp:57:13: note: in expansion of macro 'rep'
57 | rep(i, 2, sz(points)) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
7748 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7900 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
7876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
7748 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7900 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
7876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
