fork download
copy 
  1.     #include<bits/stdc++.h>
  2.     using namespace std;
  3.  
  4.     #define gc getchar_unlocked
  5.     #define pc putchar_unlocked
  6.  
  7.     inline void read(int &x){
  8.  
  9.         x=0;
  10.         register char c=gc();
  11.  
  12.         for(;c<'0' || c>'9';c=gc());
  13.  
  14.         for(;c>='0' && c<='9';c=gc())
  15.         x=(x<<3)+(x<<1)+(c-'0');
  16.     }
  17.     inline void write(int x){
  18.  
  19.         register char buffor[35];
  20.         register int i=0;
  21.  
  22.         do{
  23.  
  24.         buffor[i++]=(x%10)+'0';
  25.         x/=10;
  26.         } while(x);
  27.         i--;
  28.         while(i>=0) putchar_unlocked(buffor[i--]);
  29.         putchar_unlocked('\n');
  30.     }
  31.     int getSum(int *bit,int index){
  32.  
  33.         int sum=0;
  34.         index=index+1;
  35.  
  36.         while(index>0){
  37.  
  38.         sum+=bit[index];
  39.         index-=(index & -index);
  40.         }
  41.         return sum;
  42.     }
  43.     void update(int *bit,int size,int index,int val){
  44.  
  45.         index=index+1;
  46.         if(index<=0) return ;
  47.  
  48.         while(index<=size){
  49.  
  50.             bit[index]+=val;
  51.             index+=(index & -index);
  52.         }
  53.         return;
  54.     }
  55.     int * construct(int *arr,int size){
  56.  
  57.         int *bit=(int*)malloc((size+1)*sizeof(int));
  58.  
  59.         for(int i=0;i<=size;i++) bit[i]=0;
  60.  
  61.         for(int i=0;i<size;i++)
  62.         update(bit,size,i,arr[i]);
  63.  
  64.         return bit;
  65.     }
  66.     int main(){
  67.  
  68.         int t,n,u,l,r,v,m;
  69.         read(t);
  70.  
  71.         int *arr=(int*)malloc(10000*sizeof(int));
  72.  
  73.         while(t--){
  74.  
  75.             read(n); read(u);
  76.  
  77.             for(int i=0;i<n;i++) arr[i]=0;
  78.  
  79.             int *bit=construct(arr,n);
  80.  
  81.             while(u--){
  82.  
  83.                 read(l); read(r);read(v);
  84.  
  85.                 update(bit,n,l,v);
  86.                 update(bit,n,r+1,-v);
  87.             }
  88.             read(m);
  89.             while(m--){
  90.  
  91.                 read(u);
  92.                 write(getSum(bit,u));
  93.             }
  94.         }
  95.         return 0;
  96.     }
  97.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
1
5 3
0 1 7
2 4 6
1 3 2
3
0
3
4
stdout
copy 
7
8
6
https://ideone.com/FxjYW4
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!