fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #define maxN 100005
  4.  
  5. using namespace std;
  6. struct zgrada{
  7. long long a,b,h,r;
  8. };
  9. struct segment{
  10. long long m,l;
  11. };
  12. zgrada a[maxN];
  13. segment seg[4*maxN];
  14. long long n,i,x,y,ans,b[maxN],c[maxN],l[maxN],d[maxN],p[maxN],sa[maxN],sb[maxN],h[maxN];
  15.  
  16. void propagate(long long n,long  long l,long long d){
  17. seg[n].m+=seg[n].l;
  18. if(l==d){
  19. seg[n].l=0;
  20. }
  21. else{
  22. seg[2*n].l+=seg[n].l;
  23. seg[2*n+1].l+=seg[n].l;
  24. seg[n].l=0;
  25. }
  26. }
  27. void updatel(long long n,long long l,long long d,long long x,long long y,long long v){
  28. propagate(n,l,d);
  29. if (x <= l && d <= y) {
  30.         seg[n].l+= v;
  31.     } else {
  32.         int m = (l+d) / 2;
  33.         if (x <= m) {
  34.             updatel(2*n,l,m,x, y, v);
  35.         }
  36.         if (y >= m + 1) {
  37.             updatel(2*n+1,m+1,d, x, y, v);
  38.         }
  39.         propagate(2*n,l,m);
  40.         propagate(2*n+1,m+1,d);
  41.         seg[n].m=max(seg[2*n].m,seg[2*n+1].m);
  42.     }
  43. }
  44. void update(long long n,long long l,long long d,long long x,long long y){
  45. propagate(n,l,d);
  46. if(l==d){
  47.     seg[n].m=max(seg[n].m,y);
  48. }
  49. else{
  50.     long long m=(l+d)/2;
  51.     if(x<=m) update(2*n,l,m,x,y);
  52.     else update(2*n+1,m+1,d,x,y);
  53.     propagate(2*n,l,m);
  54.     propagate(2*n+1,m+1,d);
  55.     seg[n].m=max(seg[2*n].m,seg[2*n+1].m);
  56. }
  57. }
  58. long long query(long long n,long long l,long long d,long long x,long long y){
  59. propagate(n,l,d);
  60. if(x<=l && y>=d){
  61.     return seg[n].m;
  62. }
  63. else{
  64.     long long ans=0,m=(l+d)/2;
  65.     if(x<=m) ans=query(2*n,l,m,x,y);
  66.     if(y>=m+1) ans=max(ans,query(2*n+1,m+1,d,x,y));
  67.     return ans;
  68. }
  69. }
  70.  
  71. int main()
  72. {
  73.     std::ios::sync_with_stdio(false);
  74.     cin>>n;
  75.     p[0]=0;
  76.     for(i=0;i<n;i++){
  77.         cin>>a[i].h>>a[i].r>>a[i].a>>a[i].b;
  78.         p[i+1]=p[i]+a[i].r;
  79.         h[i]=a[i].h;
  80.     }
  81.     sort(h,h+n);
  82.     for(i=0;i<4*maxN;i++){
  83.         seg[i].m=seg[i].l=LLONG_MIN;
  84.     }
  85.     for(i=0;i<n;i++){
  86.       x=lower_bound(h,h+n,a[i].h)-h;
  87.       y=upper_bound(h,h+n,a[i].h)-h;
  88.       l[i]=max((long long)0,query(1,0,n-1,0,x))+a[i].a+a[i].r;
  89.       updatel(1,0,n-1,y,n-1,a[i].r);
  90.       update(1,0,n-1,x,l[i]);
  91.     }
  92.     for(i=0;i<4*maxN;i++){
  93.         seg[i].m=seg[i].l=LLONG_MIN;
  94.     }
  95.     for(i=n-1;i>=0;i--){
  96.       x=lower_bound(h,h+n,a[i].h)-h;
  97.       y=upper_bound(h,h+n,a[i].h)-h;
  98.       d[i]=max((long long)0,query(1,0,n-1,0,x))+a[i].b+a[i].r;
  99.       updatel(1,0,n-1,y,n-1,a[i].r);
  100.       update(1,0,n-1,x,d[i]);
  101.     }
  102.     long long ans=0;
  103.     memset(b,-1,sizeof(b));
  104.     memset(c,-1,sizeof( c ));
  105.     for(i=0;i<n;i++){
  106.         x=lower_bound(h,h+n,a[i].h)-h;
  107.         if(b[x]==-1) b[x]=i;
  108.         sa[x]+=a[i].a;
  109.         sb[x]+=a[i].b;
  110.         c[x]=i;
  111.     }
  112.     for(i=0;i<n;i++){
  113.         if(b[i]==-1 || c[i]==-1) continue;
  114.         x=p[c[i]]-p[b[i]+1]+sa[i]+sb[i]-a[b[i]].a-a[c[i]].b;
  115.         x+=l[b[i]]+d[c[i]];
  116.         ans=max(ans,x);
  117.     }
  118.     cout<<ans-p[n]<<endl;
  119.     return 0;
  120. }
Success #stdin #stdout 0s 10836KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/EAGfuX
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!