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;
const int NMAX = 2e5;
long long det(pair<int,int> a,pair<int,int> b,pair<int,int> c){
return 1LL * a.first * (b.second - c.second) + 1LL * b.first * (c.second - a.second) + 1LL * c.first * (a.second - b.second);
}
bool cmp(pair<int,int> a,pair<int,int> b){
return det(make_pair(0,0),a,b) > 0;
}
struct node_t{
int lst_ind;
vector<pair<long long,long long> > points;
node_t operator + (const node_t &other)const{
node_t ans;
ans.lst_ind = 0;
for(auto it:points){
ans.points.push_back(it);
}
for(auto it:other.points){
ans.points.push_back(it);
}
sort(ans.points.begin(),ans.points.end(),cmp);
vector<pair<long long,long long> > tmp;
tmp.push_back({0,0});
for(auto it:ans.points){
while((int)tmp.size() > 2 && det(tmp[(int)tmp.size() - 2],tmp[(int)tmp.size() - 1],it) < 0){
tmp.pop_back();
}
tmp.push_back(it);
}
reverse(tmp.begin(),tmp.end());
tmp.pop_back();
reverse(tmp.begin(),tmp.end());
ans.points.swap(tmp);
return ans;
}
long long query(pair<long long,long long> v){
while(lst_ind + 1 < (int)points.size() && points[lst_ind].first * v.first + points[lst_ind].first * v.second <= points[lst_ind + 1].first * v.first + points[lst_ind + 1].second * v.second){
lst_ind++;
}
return points[lst_ind].first * v.first + points[lst_ind].second * v.second;
}
node_t(){
lst_ind = 0;
points = vector<pair<long long,long long> >();
}
};
class SegmentTree{
int n;
vector<node_t> aint;
void build(int nod,int st,int dr,vector<pair<long long,long long> > &v){
if(st == dr){
aint[nod].points = {v[st]};
return ;
}
int mid = (st + dr) / 2;
build(nod * 2,st,mid,v);
build(nod * 2 + 1,mid + 1,dr,v);
aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}
long long query(int nod,int st,int dr,int l,int r,pair<long long,long long> v){
if(dr < l || st > r){
return 0;
}
if(l <= st && dr <= r){
return aint[nod].query(v);
}
int mid = (st + dr) / 2;
return max(query(nod * 2,st,mid,l,r,v),query(nod * 2 + 1,mid + 1,dr,l,r,v));
}
public:
SegmentTree(int n,vector<pair<long long,long long> > v){
this->n = n;
this->aint = vector<node_t>(4 * n + 5,node_t());
build(1,1,n,v);
}
long long query(int l,int r,pair<long long,long long> v){
return query(1,1,n,l,r,v);
}
};
int n;
int a[NMAX + 5];
int b[NMAX + 5];
long long solve(int st,int dr){
if(st == dr){
return 1LL * a[st] * b[st];
}
int mid = (st + dr) / 2;
long long ans = max(solve(st,mid),solve(mid + 1,dr));
int mi_a = 1e9;
int mi_b = 1e9;
int i_a = mid;
int i_b = mid;
vector<pair<long long,long long> > points = {};
int mip_b = 1e9;
for(int i = mid;i >= st;i--){
mip_b = min(mip_b,b[i]);
points.push_back({1LL * mip_b,1LL * mip_b * (1 - i)});
}
points.push_back({0LL,0LL});
reverse(points.begin(),points.end());
SegmentTree aint(mid - st + 1,points);
for(int i = mid + 1;i <= dr;i++){
mi_a = min(mi_a,a[i]);
mi_b = min(mi_b,b[i]);
while(i_a > st && a[i_a] >= mi_a){
i_a--;
}
while(i_b > st && b[i_b] > mi_b){
i_b--;
}
if(i_a <= i_b){
ans = max(ans,1LL * mi_a * mi_b * (i - i_b));
}
if(i_a + 1 <= i_b){
ans = max(ans,aint.query(i_a + 1 - (st - 1),i_b - (st - 1),make_pair(1LL * mi_a * i,1LL * mi_a)));
}
///[i_a + 1,i_b]
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d %d",&a[i],&b[i]);
}
long long ans = 0;
ans = max(ans,solve(1,n));
ans = max(ans,solve(1,n));swap(a,b);
ans = max(ans,solve(1,n));reverse(a + 1,a + 1 + n);reverse(b + 1,b + 1 + n);
ans = max(ans,solve(1,n));swap(a,b);
printf("%lld\n",ans);
return 0;
}
Compilation message (stderr)
histogram.cpp: In function 'int main()':
histogram.cpp:160:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
histogram.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | scanf("%d %d",&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |