fork download 
  1.  #include<bits/stdc++.h>
  2.         using namespace std;
  3.         #define int long long
  4.         #define MAXI (7e8)
  5.         #define N 50010
  6.  
  7.         int n, a[N];
  8.  
  9.         struct node{
  10.             int sum, prefix, suffix, ans;
  11.         };
  12.  
  13.         node seg[5*N];
  14.  
  15.         node data(int x)
  16.         {
  17.             node pawan;
  18.             pawan.sum = pawan.prefix = pawan.suffix = pawan.ans = x;
  19.             return pawan;
  20.         }
  21.  
  22.         node merge(node x, node y)
  23.         {
  24.             node pawan;
  25.  
  26.             if(x.sum==-MAXI)
  27.             {
  28.                 pawan.sum = y.sum;
  29.                 pawan.prefix = y.prefix;
  30.                 pawan.suffix = max(y.suffix , y.sum);
  31.                 pawan.ans = max(y.ans,y.prefix);    
  32.             }
  33.             else
  34.             if(y.sum == -MAXI)
  35.             {
  36.                 pawan.sum = x.sum;
  37.                 pawan.prefix = x.prefix;
  38.                 pawan.suffix = max(x.suffix , x.sum);
  39.                 pawan.ans = max(x.ans,x.prefix); 
  40.             }
  41.             else
  42.             {
  43.                 pawan.sum = x.sum + y.sum;
  44.                 pawan.prefix = max(x.prefix , x.sum + y.prefix);
  45.                 pawan.suffix = max(y.suffix , y.sum + x.suffix);
  46.                 pawan.ans = max(max(x.ans, y.ans) , x.suffix + y.prefix);
  47.             }
  48.  
  49.             return pawan;
  50.         }
  51.  
  52.         void build(int id, int l, int r)
  53.         {
  54.  
  55.             if(l==r)
  56.             {
  57.                 seg[id] = data(a[l]);
  58.                 return ;
  59.             }
  60.             int mid = (l+r)/2;
  61.             build(2 * id,l,mid);
  62.             build(2 * id + 1,mid+1,r);
  63.  
  64.             seg[id] = merge(seg[2*id], seg[2*id+1]);
  65.  
  66.         }
  67.  
  68.         void update(int x, int y, int id, int l, int r)
  69.         {    
  70.  
  71.             if(l==r)
  72.             {
  73.                 seg[id] = data(y);
  74.                 return ;
  75.             }
  76.  
  77.             int mid = (l+r)/2;
  78.             if(x<=mid)
  79.                 update(x,y,2 * id,l,mid);
  80.             else
  81.                 update(x,y,2 * id + 1,mid+1,r);
  82.  
  83.             seg[id] = merge(seg[2*id], seg[2*id+1]);
  84.         }
  85.  
  86.         node segment(int x, int y, int id, int l, int r)
  87.         {
  88.             if(l>r or l > y || x > r)  
  89.                 return data(-MAXI);
  90.  
  91.             if(x <= l && r <= y)
  92.                 return seg[id];
  93.  
  94.             int mid = (l+r)/2;
  95.             node a = segment(x,y,2 * id,l,mid);
  96.             node b = segment(x,y,2 * id + 1,mid+1,r);
  97.  
  98.             return merge(a,b);  
  99.         }
  100.  
  101.  
  102.         // Driver code to test above functions
  103.         int32_t main()
  104.         {
  105.  
  106.             #ifndef ONLINE_JUDGE
  107.             // for getting input from inpu.txt
  108.             freopen("input.txt", "r", stdin);
  109.             // for writing output to output.txt
  110.             //freopen("output.txt", "w", stdout);
  111.             #endif
  112.  
  113.             ios_base::sync_with_stdio(0);
  114.             cin.tie(NULL);
  115.             cout.tie(NULL);
  116.  
  117.             cin >> n;
  118.             for(int i=0;i<n;i++)
  119.                 cin >> a[i];// a[i];
  120.  
  121.             build(1,0,n-1);
  122.  
  123.             int q;
  124.             cin >> q;
  125.             while(q--)
  126.             {
  127.                 int type, x, y;
  128.                 cin >> type >> x >> y;
  129.                 x--;y--;
  130.                 if(type==0)
  131.                 {
  132.                     y++;
  133.                     update(x,y,1,0,n-1);
  134.                 }
  135.                 else
  136.                     cout << segment(x,y,1,0,n-1).ans << endl;
  137.             }
  138.  
  139.             return 0;  
  140.         }
Success #stdin #stdout 0s 23440KB
comments (?)
stdin 
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
stdout 
6
4
-3
https://ideone.com/orAedg
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!