#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class T1 , class T2>
bool maximize(T1& a , T2 b)
{
if (a < b) return a = b , true;
return false;
}
template<class T1 , class T2>
bool minimize(T1& a , T2 b)
{
if (a > b) return a = b , true;
return false;
}
const int maxn = 2e5;
//... CONVEXHULL
namespace ConvexHull
{
struct Line
{
i64 a ;
i64 b;
Line(i64 a , i64 b) : a(a) , b(b) {};
};
struct Hull
{
Line X ;
long double intersec;
};
class Convexhull
{
public:
vector<Hull> line;
long double getintersec(Line x , Line y)
{
return (long double)(y.b - x.b) / (x.a - y.a);
}
i64 f(Line a , i64 x)
{
return a.a * x + a.b;
}
void addline(Line x)
{
int n = line.size();
while (n > 1 && getintersec(line[n - 2].X , line[n - 1].X) >= getintersec(line[n - 2].X , x))
{
--n;
line.pop_back();
}
if (line.empty()) line.push_back({x , LLONG_MIN});
else line.push_back({x , getintersec(x , line[n - 1].X)});
return;
}
i64 find(i64 val)
{
int l = 0 , r = line.size()-1 , pos = 0;
while (l<=r)
{
int m = l + r >> 1;
if (line[m].intersec <= val)
pos = m , l = m + 1;
else r = m - 1;
}
return f(line[pos].X , val);
}
void add(i64 a , i64 b)
{
addline(Line{a,b});
return;
}
};
}
using namespace ConvexHull;
const i64 INF = 1e18 + 7;
int n;
i64 a[maxn+2],b[maxn+2];
i64 mnA[maxn+2][2] , mnB[maxn+2][2];
void build_LEFT(int l , int r)
{
mnA[r+1][0] = mnB[r+1][0] = INF;
for (int i = r; i >= l; --i)
{
mnA[i][0]=min(mnA[i+1][0],a[i]);
mnB[i][0]=min(mnB[i+1][0],b[i]);
}
return;
}
void build_RIGHT(int l , int r)
{
mnA[l-1][1] = mnB[l-1][1] = INF;
for (int i = l; i <= r; ++i)
{
mnA[i][1]=min(mnA[i-1][1],a[i]);
mnB[i][1]=min(mnA[i-1][1],b[i]);
}
return;
}
i64 case1(int l , int m , int r) // LEFT IN MINA , RIGHT IN MINB
{
Convexhull bag;
i64 res = 0;
int j = m;
for (int i = m; i >= l; --i)
{
bool ok = false;
while (j <= r && mnA[i][0] <= mnA[j][1] && mnB[i][0] >= mnB[j][1])
{
bag.add(-mnB[j][1] , mnB[j][1] * (j + 1));
++j;
ok = true;
}
if (bag.line.size() && ok)
{
res = max({
res , mnA[i][0] * bag.find(i)
});
// cout << '(' << i << ',' << j - 1 << " || VALUE ARE : " << mnA[i][0] << ',' << mnB[j - 1][1] << ',' <<mnA[i][0] * bag.find(i) << ')' << '\n';
// cout << '(' << i << ',' << j - 1 << " || VALUE ARE : " << mnA[i][0] *bag.line[bag.find(i)].X.a * i<<','<<bag.line[bag.find(i)].X.b << ')' << '\n';
}
}
return res;
}
i64 case2(int l , int m , int r) // LEFT IS MINB , RIGHT IS MINA
{
Convexhull bag;
i64 res = 0;
int j = m;
for (int i = m; i >= l; --i)
{
bool ok = false;
while (j <= r && mnB[i][0] <= mnB[j][1] && mnA[i][0] >= mnA[j][1])
{
ok = true;
bag.add(-mnA[j][1] , mnA[j][1] * (j + 1));
++j;
}
if (bag.line.size() && ok)
{
res = max({
res , mnB[i][0] * bag.find(i)
});
// cout << '(' << i << ',' << j - 1 << " || VALUE ARE : " << mnB[i][0] << ',' << mnA[j - 1][1] << ',' << mnB[i][0]*bag.find(i) << ')' << '\n';
}
}
return res;
}
i64 solve(int l , int r)
{
if (l > r) return 0;
if (l==r) return a[l] * b[r];
int m = l + r >> 1;
build_LEFT(l,m);
build_RIGHT(m,r);
// cout << "TURN\n";
// cout << l << ' ' << m << ' ' << r << '\n';
i64 res = 0;
// cout << "CASE1\n";
res = max(res , case1(l,m,r));
// cout << "CASE2\n";
res = max(res , case2(l,m,r));
// cout<<'\n';
// cout << "END CASE\n";
res = max({res , solve(l,m) , solve(m+1,r)});
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "main"
if (fopen(name".inp","r"))
{
(void)freopen(name".inp","r",stdin);
(void)freopen(name".out","w",stdout);
}
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
// for (int i = 1; i <= n; ++i) cout << a[i] << ' ' << b[i] << '\n';
cout << solve(1,n);
}
Compilation message
histogram.cpp: In member function 'i64 ConvexHull::Convexhull::find(i64)':
histogram.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'i64 solve(int, int)':
histogram.cpp:161:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
161 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'int main()':
histogram.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | (void)freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | (void)freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
