This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
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;
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;
}
void reset()
{
line.clear();
}
};
Convexhull operator + (Convexhull a , Convexhull b)
{
Convexhull c;
int id1 = 0 , id2 = 0;
for (; id1 < a.line.size() && id2 < b.line.size() ; )
{
if (a.line[id1].X.a < b.line[id2].X.a)
{
c.addline(a.line[id1++].X);
}
else {
c.addline(b.line[id2++].X);
}
}
for (; id1 < a.line.size(); ++id1) c.addline(a.line[id1].X);
for (; id2 < b.line.size(); ++id2) c.addline(b.line[id2].X);
return c;
}
const i64 INF = 1e18 + 7;
int n;
i64 a[maxn+2],b[maxn+2];
i64 mnA[maxn+2][2] , mnB[maxn+2][2];
//... BUILD SEGMENT_TREE
Convexhull stA[maxn*4+2];
Convexhull stB[maxn*4+2];
void buildA(int id , int l , int r , int u , int v)
{
stA[id].reset();
if (l > v || r < u) return;
if (l==r)
{
stA[id].add(-mnA[l][1] , mnA[l][1] * (l+1));
return;
}
else {
int m = l + r >> 1;
buildA(id*2,l,m,u,v);
buildA(id*2+1,m+1,r,u,v);
stA[id] = stA[id*2] + stA[id*2+1];
return;
}
}
void buildB(int id , int l , int r , int u , int v)
{
stB[id].reset();
if (l > v || r < u) return ;
if (l==r)
{
stB[id].add(-mnB[l][1] , mnB[l][1] * (l+1));
return;
}
else {
int m = l + r >> 1;
buildB(id*2,l,m,u,v);
buildB(id*2+1,m+1,r,u,v);
stB[id] = stB[id*2] + stB[id*2+1];
return;
}
}
i64 getA(int id , int l , int r , int u , int v , i64 k)
{
if (l > v || r < u) return -INF;
if (u <= l && r <= v) return stA[id].find(k);
int m = l + r >> 1;
return max(getA(id*2,l,m,u,v,k),getA(id*2+1,m+1,r,u,v,k));
}
i64 getB(int id , int l , int r , int u , int v , i64 k)
{
if (l > v || r < u) return -INF;
if (u <= l && r <= v) return stB[id].find(k);
int m = l + r >> 1;
return max(getB(id*2,l,m,u,v,k),getB(id*2+1,m+1,r,u,v,k));
}
//...;
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(mnB[i-1][1],b[i]);
}
buildA(1,1,n,l,r);
buildB(1,1,n,l,r);
return;
}
i64 case1(int l , int m , int r) // LEFT IS MINA , RIGHT IS MINB
{
i64 res = 0;
int j = r;
for (int i = l; i <= m; ++i)
{
while (j > m && mnA[j][1] < mnA[i][0]) --j;
int low = m + 1 , high = j , pos = -1;
while (low <= high)
{
int mid = low + high >> 1;
if (mnB[i][0] >= mnB[mid][1])
{
pos = mid;
high = mid - 1;
}
else low = mid + 1;
}
if (pos == -1) continue;
i64 x = getB(1,1,n,pos,j,i);
if (x < 0) continue;
res = max(res , x * mnA[i][0]);
}
return res;
}
i64 case2(int l , int m , int r) // LEFT IS MINB , RIGHT IS MINA
{
i64 res = 0;
int j = r;
for (int i = l; i <= m; ++i)
{
while (j > m && mnB[j][1] < mnB[i][0]) --j;
int low = m + 1 , high = j , pos = -1;
while (low <= high)
{
int mid = low + high >> 1;
if (mnA[i][0] >= mnA[mid][1])
{
pos = mid;
high = mid - 1;
}
else low = mid + 1;
}
if (pos == -1) continue;
i64 x = getA(1,1,n,pos,j,i);
if (x < 0) continue;
res = max(res , x * mnB[i][0]);
}
return res;
}
i64 case3(int l , int m , int r) // LEFT IS MINA-MINB
{
int j = r;
i64 res = 0;
for (int i = l; i <= m; ++i)
{
while (j > m && (mnA[j][1] < mnA[i][0] || mnB[j][1] < mnB[i][0])) --j;
res = max(res , mnB[i][0] * mnA[i][0] * (j - i + 1));
}
return res;
}
i64 case4(int l , int m , int r) // RIGHT IS MINB-MINA
{
int j = l;
i64 res = 0;
for (int i = r; i >= m; --i)
{
while (j < m && (mnA[j][0] < mnA[i][1] || mnB[j][0] < mnB[i][1])) ++j;
res = max(res , mnB[i][1] * mnA[i][1] * (i - j + 1));
}
return res;
}
i64 solve(int l , int r)
{
if (l > r) return 0;
if (l==r) return a[l]*b[l];
int m = l + r >> 1;
build_LEFT(l,m);
build_RIGHT(m,r);
i64 res = 0;
res = max(res , case1(l,m,r));
res = max(res , case2(l,m,r));
res = max(res , case3(l,m,r));
res = max(res , case4(l,m,r));
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];
cout << solve(1,n);
}
Compilation message (stderr)
histogram.cpp: In member function 'i64 Convexhull::find(i64)':
histogram.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'Convexhull operator+(Convexhull, Convexhull)':
histogram.cpp:84:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (; id1 < a.line.size() && id2 < b.line.size() ; )
| ~~~~^~~~~~~~~~~~~~~
histogram.cpp:84:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (; id1 < a.line.size() && id2 < b.line.size() ; )
| ~~~~^~~~~~~~~~~~~~~
histogram.cpp:94:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (; id1 < a.line.size(); ++id1) c.addline(a.line[id1].X);
| ~~~~^~~~~~~~~~~~~~~
histogram.cpp:95:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (; id2 < b.line.size(); ++id2) c.addline(b.line[id2].X);
| ~~~~^~~~~~~~~~~~~~~
histogram.cpp: In function 'void buildA(int, int, int, int, int)':
histogram.cpp:119:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
119 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'void buildB(int, int, int, int, int)':
histogram.cpp:136:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
136 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'i64 getA(int, int, int, int, int, i64)':
histogram.cpp:147:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
147 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'i64 getB(int, int, int, int, int, i64)':
histogram.cpp:154:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
154 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'i64 case1(int, int, int)':
histogram.cpp:192:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
192 | int mid = low + high >> 1;
| ~~~~^~~~~~
histogram.cpp: In function 'i64 case2(int, int, int)':
histogram.cpp:217:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
217 | int mid = low + high >> 1;
| ~~~~^~~~~~
histogram.cpp: In function 'i64 solve(int, int)':
histogram.cpp:260:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
260 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'int main()':
histogram.cpp:280:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
280 | (void)freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:281:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
281 | (void)freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
