#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
struct Line {
ll m, b;
ll eval(ll x) {
return m * x + b;
}
};
double isect(Line a, Line b) {
return (double)(a.b - b.b) / (b.m - a.m);
}
int n, a[200000], b[200000];
ll ans = 0;
void cmp(vector<int>& la, vector<int>& lb, vector<int>& ra, vector<int>& rb) {
for (int i = 0, j = 0; i < la.size(); ++i) {
while(j < ra.size() && ra[j] >= la[i] && rb[j] >= lb[i]) ++j;
ans = max(ans, (ll)(i + j + 1) * la[i] * lb[i]);
}
deque<Line> dq;
for (int i = 0, j = 0; i < la.size(); ++i) {
while(j < ra.size() && ra[j] >= la[i]) {
Line cur = {rb[j], (ll)rb[j] * (j + 2)};
while(dq.size() > 1) {
if (cur.m == dq[0].m) {
if (cur.b <= dq[0].b) break;
dq.pop_front();
}
else {
if (isect(cur, dq[1]) >= isect(dq[0], dq[1])) dq.pop_front();
else break;
}
}
dq.push_front(cur);
while(!dq.empty() && dq.back().m > lb[i])
dq.pop_back();
++j;
}
if (dq.empty()) continue;
int l = 0, r = dq.size() - 1;
while(l < r) {
int mid = (l + r + 1) / 2;
double x = mid == 0 ? -1e9 : isect(dq[mid - 1], dq[mid]);
if (x <= i) l = mid;
else r = mid - 1;
}
ans = max(ans, la[i] * dq[l].eval(i));
}
}
void solve(int l, int r) {
if (l == r) {
ans = max(ans, (ll)a[l] * b[l]);
return;
}
int mid = (l + r) / 2;
vector<int> la(1, a[mid]), lb(1, b[mid]), ra(1, a[mid + 1]), rb(1, b[mid + 1]);
for (int i = mid - 1; i >= l; --i) {
la.push_back(min(la.back(), a[i]));
lb.push_back(min(lb.back(), b[i]));
}
for (int i = mid + 2; i <= r; ++i) {
ra.push_back(min(ra.back(), a[i]));
rb.push_back(min(rb.back(), b[i]));
}
cmp(la, lb, ra, rb);
cmp(ra, rb, la, lb);
solve(l, mid);
solve(mid + 1, r);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
solve(0, n - 1);
cout << ans;
return 0;
}
Compilation message
histogram.cpp: In function 'void cmp(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
histogram.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i = 0, j = 0; i < la.size(); ++i) {
| ~~^~~~~~~~~~~
histogram.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | while(j < ra.size() && ra[j] >= la[i] && rb[j] >= lb[i]) ++j;
| ~~^~~~~~~~~~~
histogram.cpp:27:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int i = 0, j = 0; i < la.size(); ++i) {
| ~~^~~~~~~~~~~
histogram.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | while(j < ra.size() && ra[j] >= la[i]) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
