fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mx 100009
  4. #define inf 0x3f3f3f3f
  5. typedef long long ll;
  6. ll arr[mx];
  7. ll tree[3*mx]; //why? ;)
  8.  
  9. void build_tree(ll node,ll a,ll b){  //node=current node, b-e=current range
  10.         if(a>b) return;  //out of range
  11.         if(a==b){   //Leaf node
  12.             tree[node]=arr[a];  //initialize value
  13.             return;
  14.         }
  15.         ll mid=(a+b)/2;
  16.         ll left=node*2;
  17.         ll right=(node*2)+1;
  18.         build_tree(left,a,mid);   //Init left child
  19.         build_tree(right,mid+1,b); //Init right child
  20.         tree[node]=(tree[left]+tree[right]);  //Init root value
  21. }
  22.  
  23. void update_tree(ll node,ll a,ll b,ll i,ll j,ll value){ //[a,b]=current range [i,j]=to be updated
  24.         if(a>b or a>j or b<i)  //current segment is not within range [i,j]
  25.             return;
  26.         if(a==b){    //Leaf node
  27.             tree[node]+=value;
  28.             return;
  29.         }
  30.         ll mid=(a+b)/2;
  31.         ll left=node*2;
  32.         ll right=(node*2)+1;
  33.         update_tree(left,a,mid,i,j,value);   //updating left child
  34.         update_tree(right,mid+1,b,i,j,value); //updating right child
  35.         tree[node]=(tree[left]+tree[right]);  //updating root with max value
  36.  
  37. }
  38.  
  39. ll query_tree(ll node,ll a,ll b,ll i,ll j){
  40.      if(a>b or a>j or b<i) return 0; //out of range
  41.  
  42.      if(a>=i and b<=j) //current segment is totally in range [i,j]
  43.         return tree[node];
  44.  
  45.     ll left=node*2;
  46.     ll right=node*2+1;
  47.     ll mid =(a+b)/2;
  48.     ll q1=query_tree(left,a,mid,i,j);
  49.     ll q2=query_tree(right,mid+1,b,i,j);
  50.     ll res=(q1+q2);
  51.     return res;
  52. }
  53.  
  54. int main()
  55. {
  56.     ll n,q,com,x,v,y,tc,cs=0;
  57.     scanf("%lld",&tc);
  58.     while(tc--){
  59.     scanf("%lld%lld",&n,&q);
  60.     for(int i=0;i<n;i++) scanf("%d",&arr[i]);
  61.     build_tree(1,0,n-1);
  62.     printf("Case %lld:\n",++cs);
  63.     while(q--){
  64.         scanf("%lld",&com);
  65.         if(com==1){
  66.             scanf("%lld",&x);
  67.             ll tmp=query_tree(1,0,n-1,x,x);
  68.             printf("%lld\n",tmp);
  69.             update_tree(1,0,n-1,x,x,-tmp);
  70.         }
  71.         else if(com==2){
  72.             scanf("%lld%lld",&x,&v);
  73.             update_tree(1,0,n-1,x,x,v);
  74.         }
  75.         else if(com==3){
  76.             scanf("%lld%lld",&x,&y);
  77.             printf("%lld\n",query_tree(1,0,n-1,x,y));
  78.         }
  79.     }
  80.     }
  81.     return 0;
  82. }
  83.  
  84.  
Time limit exceeded #stdin #stdout 5s 19192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HPAoJR
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!