#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans = 0;
const int N = 1e5;
vector <pair <int, int> > tree[4 * N];
int a[N], b[N];
void calc1(int l, int m, int r)
{
int it1 = m + 1;
int mina = 1e9, minb = 1e9;
for(int i = m; i >= l; i--)
{
mina = min(mina, a[i]);
minb = min(minb, b[i]);
while(it1 <= r && a[it1] >= mina && b[it1] >= minb)
{
it1++;
}
ans = max(ans, mina * (it1 - i) * minb);
}
}
int uk[N * 4];
int preffix[N];
int preffix1[N];
double inter(pair <int, int> a, pair <int, int> b)
{
return 1.0 * (b.second - a.second) / (a.first - b.first);
}
void add(int v, pair <int, int> x)
{
while(tree[v].size() > 0 && tree[v].back().first == x.first)
{
tree[v].pop_back();
}
while(tree[v].size() > 1 && inter(tree[v].back(), tree[v][tree[v].size() - 2]) >= inter(tree[v][tree[v].size() - 2], x))
{
tree[v].pop_back();
}
tree[v].push_back(x);
}
void build1(int v, int l, int r)
{
tree[v].clear();
uk[v] = 0;
if(l == r)
{
tree[v].push_back({preffix[l], preffix[l] * (l + 1)});
return;
}
build1(v * 2, l, (r + l) / 2);
build1(v * 2 + 1, (r + l) / 2 + 1, r);
int j = 0;
for(int i = 0; i < tree[v * 2].size(); i++)
{
while(j < tree[v * 2 + 1].size() && (tree[v * 2 + 1][j].first < tree[v * 2][i].first || tree[v * 2 + 1][j].first == tree[v * 2][i].first && tree[v * 2 +1][j].second < tree[v * 2][i].second))
{
add(v, tree[v * 2 + 1][j]);
j++;
}
add(v, tree[v * 2][i]);
}
while(j < tree[v * 2 + 1].size())
{
add(v, tree[v * 2 + 1][j]);
j++;
}
}
int go_to1(int v, int l, int r, int al, int ar, int x)
{
if(al > ar)
{
return 0;
}
if(l >= al && r <= ar)
{
while(uk[v] < tree[v].size() - 1 && inter(tree[v][uk[v]], tree[v][uk[v] + 1]) <= x)
{
uk[v]++;
}
pair <int, int> p = tree[v][uk[v]];
return p.first * x + p.second;
}
else if(l <= ar && r >= al)
{
return max(go_to1(v * 2, l, (r + l) / 2, al, ar, x), go_to1(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, x));
}
return 0;
}
void calc2(int l, int m, int r)
{
int minb = 1e9;
int mina = 1e9;
for(int i = m + 1; i <= r; i++)
{
minb = min(minb, b[i]);
preffix[i - m - 1] = minb;
mina = min(mina, a[i]);
preffix1[i - m - 1] = mina;
}
build1(1, 0, r - m - 1);
mina = minb = 1e9;
int it1 = 0, it2 = 0;
for(int i = m; i >= l; i--)
{
mina = min(mina, a[i]);
minb = min(minb, b[i]);
while(it1 < r - m && preffix1[it1] >= mina)
{
it1++;
}
while(it2 < r - m && preffix[it2] > minb)
{
it2++;
}
int t = go_to1(1, 0, r - m - 1, it2, it1 - 1, m - i + 1);
ans = max(ans, t * mina);
}
}
void go_to(int v, int l, int r, bool fl)
{
if(l > r)
{
return;
}
if(l == r)
{
ans = max(ans, a[l] * b[l]);
return;
}
int m = (l + r)/ 2;
calc1(l, m, r);
calc2(l, m, r);
if(l == r)
{
return;
}
go_to(v * 2,l, m - 1, fl);
go_to(v * 2 + 1, m + 1, r, fl);
}
signed main()
{
// ios_base::sync_with_stdio(0);
/// cin.tie(0);
// cout.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i] >> b[i];
}
go_to(1, 0, n - 1, 1);
reverse(a, a + n);
reverse(b, b + n);
go_to(1, 0, n - 1, 0);
cout << ans;
return 0;
}
Compilation message
histogram.cpp: In function 'void build1(long long int, long long int, long long int)':
histogram.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = 0; i < tree[v * 2].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
histogram.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | while(j < tree[v * 2 + 1].size() && (tree[v * 2 + 1][j].first < tree[v * 2][i].first || tree[v * 2 + 1][j].first == tree[v * 2][i].first && tree[v * 2 +1][j].second < tree[v * 2][i].second))
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:56:146: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
56 | while(j < tree[v * 2 + 1].size() && (tree[v * 2 + 1][j].first < tree[v * 2][i].first || tree[v * 2 + 1][j].first == tree[v * 2][i].first && tree[v * 2 +1][j].second < tree[v * 2][i].second))
histogram.cpp:63:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while(j < tree[v * 2 + 1].size())
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp: In function 'long long int go_to1(long long int, long long int, long long int, long long int, long long int, long long int)':
histogram.cpp:78:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | while(uk[v] < tree[v].size() - 1 && inter(tree[v][uk[v]], tree[v][uk[v] + 1]) <= x)
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9748 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9804 KB |
Output is correct |
| 7 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 8 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 9 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 10 |
Correct |
7 ms |
9840 KB |
Output is correct |
| 11 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 12 |
Correct |
10 ms |
9804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9836 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9748 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9804 KB |
Output is correct |
| 7 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 8 |
Correct |
7 ms |
9804 KB |
Output is correct |
| 9 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 10 |
Correct |
7 ms |
9840 KB |
Output is correct |
| 11 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 12 |
Correct |
10 ms |
9804 KB |
Output is correct |
| 13 |
Runtime error |
121 ms |
25836 KB |
Execution killed with signal 11 |
| 14 |
Halted |
0 ms |
0 KB |
- |
