fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. LL   A[100012];
  5. int   L[100012];
  6. int   R[100012];
  7. LL tree[100012];
  8. LL query(int idx)
  9. {
  10.     LL ret = 0;
  11.     for(idx+=1;idx;idx-=idx&-idx)
  12.         ret+=tree[idx];
  13.     return ret;
  14. }
  15.  
  16. void update(int idx , LL val)
  17. {
  18.     for(idx+=1;idx<=100011;idx+=idx&-idx)
  19.         tree[idx]+=val;
  20. }
  21.  
  22. int main()
  23. {
  24.  
  25.     ios::sync_with_stdio(0);cin.tie(0);
  26.     int N ,e = 1;
  27.     while(cin>>N)
  28.     {
  29.         cout<<"Case #"<<e<<":\n";
  30.         int Q, i , x , y , type;
  31.         for(i=0;i<100012;++i)tree[i] = 0;
  32.         set < int > indices;
  33.         for(i=0;i<N;++i)
  34.         {
  35.             cin>>A[i];
  36.             indices.insert(i);
  37.             L[i] = i-1;
  38.             R[i] = i+1;
  39.             update(i,A[i]);
  40. //            cout<<A[i]<<" "<<query(i)-query(i-1)<<'\n';
  41.         }
  42. //        cout<<endl;
  43.         cin>>Q;
  44.         int save;
  45.         for(;Q;--Q)
  46.         {
  47.  
  48.             cin>>type>>x>>y;
  49.             --x;--y;
  50.             if(x>y)swap(x,y);
  51.  
  52.             if(!type)
  53.             {
  54.                 auto it = indices.lower_bound(x);
  55.                 if(it==indices.end())continue;
  56.                 int strt=*it;
  57.                 while(strt<=y)
  58.                 {
  59.                     update(strt,-A[strt]);
  60.                     A[strt] = (LL)sqrt(A[strt]);
  61.                     update(strt,A[strt]);
  62.                     if(A[strt]<=1)
  63.                     {
  64.                         if(L[strt]!=-1)
  65.                             R[L[strt]]=R[strt];
  66.                         if(R[strt]!=N)
  67.                             L[R[strt]]=L[strt];
  68.                         auto jt = indices.lower_bound(strt);
  69.  
  70.                         indices.erase(jt);
  71.                     }
  72.                     strt = R[strt];
  73.                 }
  74.             }
  75.             else
  76.                 cout<<query(y)-query(x-1)<<'\n';
  77.         }
  78.         cout<<'\n';++e;
  79. //        return 0;
  80.     }
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0s 5812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3WG1q7
language:
C++14 (gcc 8.3)
created:
8 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!