Facebook
From Paltry Duck, 2 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 153
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  5. #define endl "\n"
  6. #define int long long int
  7.  
  8. struct item{
  9.         int sum,pre,suf,max_sum;
  10. };
  11.  
  12. struct segment{
  13.         int size=1;
  14.         vector<int>sum,pre,suf,ope,max_sum;
  15.        
  16.         void print()
  17.         {
  18.                 for(int i=0;i<2*size;i++)
  19.                 {
  20.                         cout<<i<<' '<<sum[i]<<' '<<pre[i]<<' '<<suf[i]<<' '<<max_sum[i]<<' '<<ope[i]<<endl;
  21.                 }
  22.         }
  23.         void init(int n)
  24.         {
  25.                 while(size<n)
  26.                 {
  27.                         size*=2;
  28.                 }
  29.                 sum.assign(2*size,0);
  30.                 ope.assign(2*size,LONG_LONG_MAX);
  31.                 pre.assign(2*size,0);
  32.                 suf.assign(2*size,0);
  33.                 max_sum.assign(2*size,0);
  34.                 return ;
  35.         }
  36.        
  37.         int operation(int a,int b,int l,int r)
  38.         {
  39.                 if(b!=LONG_LONG_MAX)
  40.                 {
  41.                         return b*(r-l);
  42.                 }
  43.                 return a;
  44.         }
  45.        
  46.         int operation2(int a,int b,int l,int r)
  47.         {
  48.                 if(b!=LONG_LONG_MAX)
  49.                 {
  50.                         if(b<0)
  51.                         {
  52.                                 return 0;
  53.                         }
  54.                         else
  55.                         {
  56.                                 return b*(r-l);
  57.                         }
  58.                 }
  59.                 else
  60.                 {
  61.                         return a;
  62.                 }
  63.         }
  64.         void propagate(int node,int l,int r)
  65.         {       if(ope[node]!=LONG_LONG_MAX)
  66.                 {
  67.                         sum[node]=ope[node]*(r-l);
  68.                         if(ope[node]<0)
  69.                         {
  70.                                 pre[node]=0;
  71.                                 suf[node]=0;
  72.                                 max_sum[node]=0;
  73.                         }
  74.                         else
  75.                         {
  76.                                 pre[node]=ope[node]*(r-l);
  77.                                 suf[node]=ope[node]*(r-l);
  78.                                 max_sum[node]=ope[node]*(r-l);
  79.                         }
  80.                 }
  81.                 if(r-l==1)
  82.                 {      
  83.                         ope[node]=LONG_LONG_MAX;
  84.                         return ;
  85.                 }
  86.                 if(ope[node]!=LONG_LONG_MAX)
  87.                 {
  88.                         ope[2*node+1]=ope[node];
  89.                         ope[2*node+2]=ope[node];
  90.                 }
  91.                 ope[node]=LONG_LONG_MAX;
  92.                 return ;
  93.         }
  94.        
  95.         void modify(int node,int l,int r,int lx,int rx,int value)
  96.         {
  97.                 propagate(node,l,r);
  98.                 if(lx<=l && r<=rx)
  99.                 {
  100.                         ope[node]=value;
  101.                         return ;
  102.                 }
  103.                 else if(l>=rx ||r<=lx)
  104.                 {
  105.                         return ;
  106.                 }
  107.                 int mid=l+(r-l)/2;
  108.                 modify(2*node+1,l,mid,lx,rx,value);
  109.                 modify(2*node+2,mid,r,lx,rx,value);
  110.                 sum[node]=operation(sum[2*node+1],ope[2*node+1],l,mid)+operation(sum[2*node+2],ope[2*node+2],mid,r);
  111.                 pre[node]=max(operation2(pre[2*node+1],ope[2*node+1],l,mid),operation(sum[2*node+1],ope[2*node+1],l,mid)+operation2(pre[2*node+2],ope[2*node+2],mid,r));
  112.                 suf[node]=max(operation2(suf[2*node+2],ope[2*node+2],mid,r),operation(sum[2*node+2],ope[2*node+2],mid,r)+operation2(suf[2*node+1],ope[2*node+1],l,mid));
  113.                 max_sum[node]=max(max(operation2(max_sum[2*node+1],ope[2*node+1],l,mid),operation2(max_sum[2*node+2],ope[2*node+2],mid,r)),operation2(pre[2*node+2],ope[2*node+2],mid,r)+operation2(suf[2*node+1],ope[2*node+1],l,mid));
  114.                 return ;
  115.         }
  116.        
  117.         void modify(int lx,int rx,int value)
  118.         {
  119.                 return modify(0,0,size,lx,rx,value);
  120.         }
  121. };
  122.  
  123. int32_t main()
  124. {
  125.         int n,m;
  126.         cin>>n>>m;
  127.         segment sg;
  128.         sg.init(n);
  129.         for(int i=0;i<m;i++)
  130.         {
  131.                 int l,r,value;
  132.                 cin>>l>>r>>value;
  133.                 sg.modify(l,r,value);
  134.                 cout<<sg.max_sum[0]<<endl;
  135.                 //sg.print();
  136.         }
  137. }
  138.                
  139.