fork download
copy 
  1. /*************
  2.         Author - am10
  3.              ******************/
  4. #include<bits/stdc++.h>
  5.  
  6. #define sync ios::sync_with_stdio(false)
  7. #define endl '\n'
  8. #define ll long long
  9. #define pb push_back
  10. #define PI acos(-1)
  11. #define pii pair <int,int>
  12.  
  13. /*
  14. //D-S-U
  15. int root(int v){return par[v] < 0 ? v : (par[v] = root(par[v]));}
  16. void merge(int x,int y){	//	x and y are some tools (vertices)
  17.         if((x = root(x)) == (y = root(y))     return ;
  18. 	if(par[y] < par[x])	// balancing the height of the tree
  19. 		swap(x, y);
  20. 	par[x] += par[y];
  21. 	par[y] = x;
  22. }
  23. */
  24. using namespace std;
  25.  
  26. ll seg[400005];
  27. bool marker[100005] = {0};
  28. int mover[100005] = {0};
  29. vector <ll> v;
  30.  
  31. ll query(int node,int start,int end,int l,int r)
  32. {
  33.    if(r < start || l > end)
  34.      return 0;
  35.    else if(l<=start && r >= end)
  36.      return seg[node];
  37.    else
  38.    {
  39.      int mid = (start + end)/2;
  40.      return query(2*node,start,mid,l,r) + query(2*node+1,mid+1,end,l,r);
  41.    }
  42.  
  43. }
  44.  
  45.  
  46. void update(int node,int start,int end,int idx)
  47. {
  48.   if(start == end)
  49.   {
  50.     seg[node] = floor(sqrt(seg[node]));
  51.     if(seg[node] == 1)
  52.     {
  53.       marker[start] = 1;
  54.       mover[start] = 1;
  55.       //cout << start << endl;
  56.       start--;
  57.       while(mover[start]!=0&&start>=1)
  58.       {
  59.         mover[start] = mover[start+1]+1;
  60.         //cout << start <<  " " << mover[start] << endl;
  61.         start--;
  62.       }
  63.     }
  64.     return;
  65.   }
  66.   else
  67.   {
  68.     int mid = (start+end)/2;
  69.     if(idx >= start && idx <= mid)
  70.        update(2*node,start,mid,idx);
  71.     else
  72.        update(2*node+1,mid+1,end,idx);
  73.     seg[node] = seg[2*node] + seg[2*node+1];   
  74.   }
  75. }
  76.  
  77. void build(int node,int start,int end)
  78. {
  79.   if(start == end)
  80.   {
  81.     seg[node] = v[start];
  82.     return;
  83.   }
  84.   else
  85.   {
  86.     int mid = (start+end)/2;
  87.     build(2*node,start,mid);
  88.     build(2*node+1,mid+1,end);
  89.     seg[node] = seg[2*node] + seg[2*node+1];
  90.   }
  91. }
  92.  
  93. int main()
  94. {
  95.   sync;
  96.   int n,cnt = 1;
  97.   while(cin >> n)
  98.   { 
  99.     v.clear();
  100.     memset(marker,0,sizeof(marker));
  101.     memset(mover,0,sizeof(mover));
  102.     v.pb(-1);
  103.     for(int i=0;i<n;i++)
  104.     {
  105.       ll a;
  106.       cin >> a;
  107.       v.pb(a);
  108.       if(a == 1)
  109.         marker[i+1] = 1;
  110.     }
  111.     build(1,1,n);
  112.  
  113.     int m;
  114.     cout << "Case #" << cnt <<":" << endl;
  115.     cnt++;
  116.     cin >> m;
  117.     for(int i=0;i<m;i++)
  118.     {
  119.       int x;
  120.       cin >> x;
  121.       if(x==0)
  122.       {
  123.         int l,r;
  124.         cin >> l >> r;
  125.         if(l>r)
  126.           swap(l,r);
  127.         for(int j=l;j<=r;)
  128.         {
  129.           if(marker[j] == 1)
  130.           {
  131.             //cout << j << " " << mover[j] << endl;
  132.             j = j+mover[j];
  133.  
  134.           }
  135.           else
  136.           {
  137.             update(1,1,n,j);
  138.             j++;
  139.           }
  140.         }
  141.       }
  142.       else
  143.       { 
  144.          int l,r;
  145.          cin >> l >> r;
  146.          if(l>r)
  147.           swap(l,r);
  148.          ll res = query(1,1,n,l,r);
  149.          cout << res << endl;
  150.  
  151.       }
  152.     }
  153.   } 
  154. }
  155.  
  156.  
Success #stdin #stdout 0s 19680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7WZFKN
problem GSS4, based on SPOJ submission 19590388 (CPP14), 2017-06-11 09:17:29
language:
C++14 (gcc 8.3)
created:
6 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!