#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
#define sz(x) (x).size()
struct Line
{
i64 a , 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 getval(Line a , i64 x)
{
return a.a * x + a.b;
}
void addline(Line a)
{
int n = sz(line);
while (n > 1 && getintersec(line[n - 2].X , a) <= getintersec(line[n - 1].X , line[n - 2].X))
line.pop_back() , --n;
if (!sz(line))
line.push_back({a , LLONG_MIN });
else line.push_back({a , getintersec(a , line[n - 1].X)});
return;
}
i64 find(i64 val)
{
int low = 0 , high = sz(line) - 1 , p = 0;
while (low <= high)
{
int mid = low + high >> 1;
if (line[mid].intersec <= val) p = mid , low = mid + 1;
else high = mid - 1;
}
return getval(line[p].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;
}
// cout<<'('<<i<<"->"<<pos<<','<<j<<')'<<'\n';
if (pos == -1) continue;
i64 x = getB(1,1,n,pos,j,i);
// cout<<'('<<i<<' '<<" ||| "<<pos<<'-'<<j<<" || "<<x<<')'<<'\n';
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;
}
// cout<<'('<<i<<"->"<<pos<<','<<j<<')'<<'\n';
if (pos == -1) continue;
i64 x = getA(1,1,n,pos,j,i);
// cout<<'('<<i<<','<<" ||| "<<pos<<'-'<<j<<" || "<<x<<')'<<'\n';
if (x < 0) continue;
res = max(res , x * mnB[i][0]);
}
return res;
}
i64 case3(int l , int m , int r)
{
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));
// cout << i << ' ' << j << ' ' << mnA[i][0] * mnB[i][0] * (j - i + 1) << '\n';
}
// for (int i = m; i <= r; ++i) cout << mnA[i][1] << ' ' << mnB[i][1] << '\n';
return res;
}
i64 case4(int l , int m , int r)
{
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));
// cout << i << ' ' << j << ' ' << mnB[i][1] << ' ' << mnA[i][1] << ' ' << (i - j + 1) << '\n';
}
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;
// cout << "CASE : " << l <<','<<m<<','<<r<<'\n';
// cout << "CASE1\n";
res = max(res , case1(l,m,r));
// cout << "CASE2\n";
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];
// 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::find(i64)':
histogram.cpp:60:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = low + high >> 1;
| ~~~~^~~~~~
histogram.cpp: In function 'Convexhull operator+(Convexhull, Convexhull)':
histogram.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (; id1 < a.line.size() && id2 < b.line.size() ; )
| ~~~~^~~~~~~~~~~~~~~
histogram.cpp:80:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (; id1 < a.line.size() && id2 < b.line.size() ; )
| ~~~~^~~~~~~~~~~~~~~
histogram.cpp:90:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (; id1 < a.line.size(); ++id1) c.addline(a.line[id1].X);
| ~~~~^~~~~~~~~~~~~~~
histogram.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hull>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | 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:115:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'void buildB(int, int, int, int, int)':
histogram.cpp:132:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
132 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'i64 getA(int, int, int, int, int, i64)':
histogram.cpp:143:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
143 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'i64 getB(int, int, int, int, int, i64)':
histogram.cpp:150:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
150 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'i64 case1(int, int, int)':
histogram.cpp:188:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
188 | int mid = low + high >> 1;
| ~~~~^~~~~~
histogram.cpp: In function 'i64 case2(int, int, int)':
histogram.cpp:215:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
215 | int mid = low + high >> 1;
| ~~~~^~~~~~
histogram.cpp: In function 'i64 solve(int, int)':
histogram.cpp:264:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
264 | int m = l + r >> 1;
| ~~^~~
histogram.cpp: In function 'int main()':
histogram.cpp:287:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
287 | (void)freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:288:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
288 | (void)freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
44120 KB |
Output is correct |
| 2 |
Correct |
11 ms |
44180 KB |
Output is correct |
| 3 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 4 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 5 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 6 |
Correct |
14 ms |
44280 KB |
Output is correct |
| 7 |
Correct |
11 ms |
44120 KB |
Output is correct |
| 8 |
Correct |
12 ms |
44196 KB |
Output is correct |
| 9 |
Correct |
12 ms |
44280 KB |
Output is correct |
| 10 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 11 |
Correct |
6 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
13 ms |
44124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
44120 KB |
Output is correct |
| 2 |
Correct |
11 ms |
44180 KB |
Output is correct |
| 3 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 4 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 5 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 6 |
Correct |
14 ms |
44280 KB |
Output is correct |
| 7 |
Correct |
11 ms |
44120 KB |
Output is correct |
| 8 |
Correct |
12 ms |
44196 KB |
Output is correct |
| 9 |
Correct |
12 ms |
44280 KB |
Output is correct |
| 10 |
Correct |
12 ms |
44124 KB |
Output is correct |
| 11 |
Correct |
6 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
13 ms |
44124 KB |
Output is correct |
| 13 |
Correct |
1110 ms |
100180 KB |
Output is correct |
| 14 |
Correct |
911 ms |
99924 KB |
Output is correct |
| 15 |
Correct |
1186 ms |
99732 KB |
Output is correct |
| 16 |
Correct |
1103 ms |
99352 KB |
Output is correct |
| 17 |
Correct |
1132 ms |
106688 KB |
Output is correct |
| 18 |
Correct |
1099 ms |
105392 KB |
Output is correct |
| 19 |
Correct |
1105 ms |
104240 KB |
Output is correct |
| 20 |
Correct |
1116 ms |
106576 KB |
Output is correct |
| 21 |
Correct |
1121 ms |
99408 KB |
Output is correct |
| 22 |
Correct |
1083 ms |
107412 KB |
Output is correct |
| 23 |
Correct |
97 ms |
48988 KB |
Output is correct |
| 24 |
Correct |
1018 ms |
100688 KB |
Output is correct |
