#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef long double ld;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)2e5 + 100;
const ld inf = (2e18);
struct Line{
ld A;
ld B;
ld lim;
};
ld cross(Line aa, Line bb){
return (aa.B-bb.B)/(bb.A-aa.A);
}
struct Hull{
vector<Line> pq;
void append(Line cur){
if(!pq.empty()){
if(pq.back().A == cur.A){
if(pq.back().B >= cur.B) return;
pq.pop_back();
}
// no two paralel lines
while(pq.size() >= 2 && cross(pq[pq.size() - 2], cur) <= cross(pq[pq.size() - 2], pq[pq.size() - 1])){
pq.pop_back();
}
}
if(!pq.empty()){
pq.back().lim = cross(pq.back(), cur);
}
pq.push_back(cur);
}
int it = 0;
ll get(ll val){
while(pq[it].lim < val)
it ++ ;
return pq[it].A*1ll*val+pq[it].B;
}
};
ll x[N];
ll y[N];
ll sol = 0;
struct ele{
ll ff;
ll gg;
ll cnt;
};
Hull segt[N * 4 + 512];
Line faf[N];
void build(int node, int cl, int cr){
segt[node].pq.clear();
segt[node].it=0;
for(int i = cr; i >= cl; i -- ){
segt[node].append(faf[i]);
}
if(cl==cr)return;
int mid = (cl+cr)/2;
build(node*2,cl,mid);
build(node*2+1,mid+1,cr);
}
ll qry(int node, int cl, int cr, int tl, int tr, ll qa){
if(cr < tl || cl > tr) return 0;
if(cl >= tl && cr <= tr){
return segt[node].get(qa);
}
int mid = (cl+cr)/2;
return max(qry(node*2,cl,mid,tl,tr,qa),qry(node*2+1,mid+1,cr,tl,tr,qa));
}
void upd(vector<ele> f1, vector<ele> f2){
int ii = -1;
for(int i = 0 ; i < f2.size(); i ++ ){
while(ii + 1 < f1.size() && f1[ii+1].ff >= f2[i].ff && f1[ii+1].gg >= f2[i].gg){
ii ++ ;
}
if(ii>=0)
sol = max(sol,(f2[i].cnt+f1[ii].cnt)*1ll*f2[i].ff*1ll*f2[i].gg);
}
for(int i = 0 ; i < f2.size(); i ++ ){
faf[i] = {f2[i].gg,f2[i].gg*1ll*f2[i].cnt,inf};
}
build(1, 0, f2.size() - 1);
ii = -1;
int jj = 0;
for(int i = 0 ; i < f1.size(); i ++ ){
while(ii + 1 < f2.size() && f2[ii + 1].ff >= f1[i].ff)
ii ++ ;
while(jj < f2.size() && f2[jj].gg > f1[i].gg){
jj ++ ;
}
if(jj <= ii){
sol = max(sol, qry(1, 0, f2.size() - 1, jj,ii,f1[i].cnt) * 1ll * f1[i].ff);
}
}
}
void solve(int lf, int rf){
if(lf >= rf) return;
int mid = (lf + rf) / 2;
ele cur = {(ll)1e9, (ll)1e9, 0};
vector<ele> pp, qq;
for(int i = mid; i >= lf ; i -- ){
cur.ff=min(cur.ff,x[i]);
cur.gg=min(cur.gg,y[i]);
cur.cnt++;
pp.push_back(cur);
}
cur = {(ll)1e9, (ll)1e9, 0};
for(int i = mid + 1; i <= rf; i ++ ){
cur.ff=min(cur.ff,x[i]);
cur.gg=min(cur.gg,y[i]);
cur.cnt++;
qq.push_back(cur);
}
upd(pp,qq);
upd(qq,pp);
solve(lf, mid);
solve(mid+1, rf);
}
int main(){
fastIO;
int n;
cin >> n;
for(int i = 1; i <= n; i ++ ){
cin >> x[i] >> y[i];
sol = max(sol, x[i] * 1ll * y[i]);
}
solve(1, n);
cout << sol << "\n";
return 0;
}
Compilation message
histogram.cpp: In function 'void upd(std::vector<ele>, std::vector<ele>)':
histogram.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0 ; i < f2.size(); i ++ ){
| ~~^~~~~~~~~~~
histogram.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while(ii + 1 < f1.size() && f1[ii+1].ff >= f2[i].ff && f1[ii+1].gg >= f2[i].gg){
| ~~~~~~~^~~~~~~~~~~
histogram.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0 ; i < f2.size(); i ++ ){
| ~~^~~~~~~~~~~
histogram.cpp:98:25: warning: narrowing conversion of 'f2.std::vector<ele>::operator[](((std::vector<ele>::size_type)i)).ele::gg' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
98 | faf[i] = {f2[i].gg,f2[i].gg*1ll*f2[i].cnt,inf};
histogram.cpp:98:40: warning: narrowing conversion of '((f2.std::vector<ele>::operator[](((std::vector<ele>::size_type)i)).ele::gg * 1) * f2.std::vector<ele>::operator[](((std::vector<ele>::size_type)i)).ele::cnt)' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
98 | faf[i] = {f2[i].gg,f2[i].gg*1ll*f2[i].cnt,inf};
histogram.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 0 ; i < f1.size(); i ++ ){
| ~~^~~~~~~~~~~
histogram.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while(ii + 1 < f2.size() && f2[ii + 1].ff >= f1[i].ff)
| ~~~~~~~^~~~~~~~~~~
histogram.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ele>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | while(jj < f2.size() && f2[jj].gg > f1[i].gg){
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
25680 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25804 KB |
Output is correct |
| 3 |
Correct |
27 ms |
25688 KB |
Output is correct |
| 4 |
Correct |
16 ms |
25676 KB |
Output is correct |
| 5 |
Correct |
16 ms |
25788 KB |
Output is correct |
| 6 |
Correct |
17 ms |
25712 KB |
Output is correct |
| 7 |
Correct |
16 ms |
25772 KB |
Output is correct |
| 8 |
Correct |
16 ms |
25660 KB |
Output is correct |
| 9 |
Correct |
17 ms |
25668 KB |
Output is correct |
| 10 |
Correct |
21 ms |
25816 KB |
Output is correct |
| 11 |
Correct |
16 ms |
25376 KB |
Output is correct |
| 12 |
Correct |
23 ms |
25752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
25680 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25804 KB |
Output is correct |
| 3 |
Correct |
27 ms |
25688 KB |
Output is correct |
| 4 |
Correct |
16 ms |
25676 KB |
Output is correct |
| 5 |
Correct |
16 ms |
25788 KB |
Output is correct |
| 6 |
Correct |
17 ms |
25712 KB |
Output is correct |
| 7 |
Correct |
16 ms |
25772 KB |
Output is correct |
| 8 |
Correct |
16 ms |
25660 KB |
Output is correct |
| 9 |
Correct |
17 ms |
25668 KB |
Output is correct |
| 10 |
Correct |
21 ms |
25816 KB |
Output is correct |
| 11 |
Correct |
16 ms |
25376 KB |
Output is correct |
| 12 |
Correct |
23 ms |
25752 KB |
Output is correct |
| 13 |
Correct |
699 ms |
59060 KB |
Output is correct |
| 14 |
Correct |
746 ms |
66008 KB |
Output is correct |
| 15 |
Correct |
714 ms |
59300 KB |
Output is correct |
| 16 |
Correct |
702 ms |
59332 KB |
Output is correct |
| 17 |
Correct |
818 ms |
66364 KB |
Output is correct |
| 18 |
Correct |
905 ms |
66252 KB |
Output is correct |
| 19 |
Correct |
769 ms |
63832 KB |
Output is correct |
| 20 |
Correct |
867 ms |
66296 KB |
Output is correct |
| 21 |
Correct |
703 ms |
59600 KB |
Output is correct |
| 22 |
Correct |
837 ms |
66160 KB |
Output is correct |
| 23 |
Correct |
65 ms |
28764 KB |
Output is correct |
| 24 |
Correct |
709 ms |
57784 KB |
Output is correct |
