fork(3) download
copy 
  1. // Implicit segment tree ,   support  range update [L-R] and point query.
  2.  
  3. // Also handle queries when  intitially array is emmpty ,  and 1 <= L , R <= 1e9
  4.  
  5. #include<bits/stdc++.h>
  6. #define ll long long
  7.  
  8. using namespace std;
  9.  
  10. struct Implicit_segment_tree {
  11.     ll Sum;
  12. 	Implicit_segment_tree *left , *right;
  13.     Implicit_segment_tree(ll _Sum , Implicit_segment_tree *_left , Implicit_segment_tree *_right ){
  14.     Sum = _Sum;
  15.     left = _left;
  16.     right = _right;
  17.     }
  18. };
  19.  
  20. void update(Implicit_segment_tree *root , int l , int r , int s , int e , ll value ){
  21.        if(s > r || l > e )
  22.            return;
  23.          if(l >= s && r <= e ){
  24.             root->Sum += value;
  25.             return;
  26.          }
  27.          if(root->left == NULL)
  28.          root->left = new Implicit_segment_tree(0 , NULL , NULL);
  29.          if(root->right == NULL)
  30.          root->right = new Implicit_segment_tree(0 , NULL , NULL);
  31.          update(root->left , l , (l + r)/2 , s , e , value );
  32.          update(root->right , (l + r)/2 + 1 , r , s, e , value);
  33. }
  34.  
  35. ll query(Implicit_segment_tree *root , int l , int r, int idx) {
  36. 	 if( root == NULL ||  idx > r || l > idx )
  37. 	  return 0;
  38. 	  if( l  == r )
  39. 	  return root->Sum;
  40. 	return root->Sum + query(root->left , l , ( l + r)/2 , idx) + query( root->right , (l + r)/2 + 1 , r, idx);
  41. }
  42.  
  43.  
  44. int main() {
  45.                   int N , Q;
  46.                     scanf("%d%d",&N,&Q);
  47.                       Implicit_segment_tree *root = new Implicit_segment_tree(0 , NULL, NULL);
  48.                       for(int i = 1 ; i <= N ; ++i ){
  49.                               int x;
  50.                               scanf("%d",&x);
  51.                                 update(root , 1 , N , i , i , x );
  52.                      }
  53.                      while(Q--){
  54.                         int choice;
  55.                          scanf("%d",&choice);                     // choice 1  for update , 2 for query at index x
  56.                         if(choice == 1){
  57.                             int L , R , value;
  58.                             scanf("%d%d%d",&L,&R,&value);
  59.                               update(root, 1 , N , L , R , value );
  60.                         } else {
  61.                                       int idx;
  62.                           scanf("%d",&idx);
  63.                             printf("%lld\n",query(root, 1 , N , idx));
  64.                         }
  65.                      }
  66.     return 0;
  67. }
Time limit exceeded #stdin #stdout 15s 1219072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Oe6jZ2
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!