fork download 
  1. #include <cmath>
  2. #include <cstring>
  3. #include <vector>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7. struct list
  8. {
  9.     long sum,bestsum,left,right;
  10. };
  11.  
  12. list* make_new_node(long s,long bs,long l,long r)
  13. {
  14.     list* temp=new list();
  15.     temp->sum=s;
  16.     temp->bestsum=bs;
  17.     temp->left=l;
  18.     temp->right=r;
  19.     return temp;
  20. }
  21.  
  22. void build(long arr[],list* tree[],int node,int low,int high)
  23. {
  24.     if(low>high)
  25.         return;
  26.     if(low==high)
  27.     {
  28.         tree[node]=make_new_node(arr[low],arr[low],arr[low],arr[low]);
  29.         return;
  30.     }
  31.  
  32.     build(arr,tree,2*node+1,low,(high+low)/2);
  33.     build(arr,tree,2*node+2,(high+low)/2+1,high);
  34.  
  35. //    tree[node]=NULL;
  36.     long a=tree[2*node+1]->sum+tree[2*node+2]->sum;
  37.     long b=max(max(tree[2*node+1]->bestsum,tree[2*node+2]->bestsum),tree[2*node+1]->right+tree[2*node+2]->left);
  38.     long c=max(tree[2*node+1]->left,tree[2*node+1]->sum+tree[2*node+2]->left);
  39.     long d=max(tree[2*node+1]->right+tree[2*node+2]->sum,tree[2*node+2]->right);
  40.  
  41.     tree[node]=make_new_node(a,b,c,d);
  42. }
  43.  
  44. list* query(list* tree[],int node,int low,int high,int l,int r)
  45. {
  46.     if(low==l && high==r)
  47.         return tree[node];
  48.     int p1 = 2*node+1, p2 = 2*node+2, mid = (low+high)/2;
  49.     if(r<=mid) 
  50.     	return query(tree,p1,low,mid,l,r);
  51.  	if(l>mid)
  52.  		return query(tree,p2,mid+1,high,l,r);
  53.     list *a=query(tree,2*node+1,low,(high+low)/2,l,mid);
  54.     list *b=query(tree,2*node+2,(high+low)/2+1,high,mid+1,r);
  55.  	list *n;
  56.     long w=a->sum+b->sum;
  57.     long x=max(max(a->bestsum,b->bestsum),a->right+b->left);
  58.     long y=max(a->left,a->sum+b->left);
  59.     long z=max(a->right+b->sum,b->right);
  60.     n=make_new_node(w,x,y,z);
  61.  
  62.     return n;
  63. }
  64.  
  65. int main() 
  66. {
  67.     //ios_base::sync_with_stdio(false);
  68.     int n;
  69.     scanf("%d",&n);
  70. //    cin>>n;
  71.     long arr[n];
  72.     list* tree[5*n];
  73.     for(int i=0;i<n;i++)
  74.         scanf("%ld",&arr[i]);
  75. //        cin>>arr[i];
  76.     build(arr,tree,0,0,n-1);
  77.  
  78.     int q;
  79.     scanf("%d",&q);
  80.     for(int i=0;i<q;i++)
  81.     {
  82.         int l,r;
  83.         scanf("%d%d",&l,&r);
  84. //        cout<<query(tree,0,0,n-1,l-1,r-1)->bestsum<<endl;
  85.         printf("%ld\n",query(tree,0,0,n-1,l-1,r-1)->bestsum);
  86.     }
  87.     return 0;
  88. }
Runtime error #stdin #stdout 0s 16064KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/YilRLC
language:
C++14 (gcc 8.3)
created:
7 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!