Submission #316356

#TimeUsernameProblemLanguageResultExecution timeMemory
316356georgerapeanu3D Histogram (COCI20_histogram)C++11
20 / 110
2566 ms52900 KiB
#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; 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; 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); } ans.points.swap(tmp); ans.lst_ind = (int)ans.points.size() - 1; 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].second * v.second <= points[lst_ind + 1].first * v.first + points[lst_ind + 1].second * v.second) { lst_ind++; } while(lst_ind - 1 >= 0 && points[lst_ind].first * v.first + points[lst_ind].second * 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; int i2_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--; } while(i2_b >= st && b[i2_b] >= mi_b) { i2_b--; } ans = max(ans,1LL * mi_a * mi_b * (i - max(i_a,i2_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:161:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
histogram.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         scanf("%d %d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...