fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct tree
  4. {
  5.     int c2;
  6.     int c5;
  7.     int c0;
  8.     int lazy;
  9. };
  10. tree st[400005];
  11. int a[100005];
  12. void construct(int s,int e,int i)
  13. {
  14.     if(s==e)
  15.     {
  16.         int x=a[s];
  17.         st[i].lazy=-1;
  18.         st[i].c2=0;
  19.         st[i].c5=0;
  20.         if(a[s]==0)
  21.             st[i].c0=1;
  22.             else
  23.                 st[i].c0=0;
  24.         while(x%5==0&&x)
  25.         {
  26.            x=x/5;
  27.            st[i].c5++;
  28.         }
  29.         while(x%2==0&&x)
  30.         {
  31.            x=x/2;
  32.            st[i].c2++;
  33.         }
  34.         return;
  35.     }
  36.     int mid=(s+e)/2;
  37.     construct(s,mid,2*i);
  38.     construct(mid+1,e,2*i+1);
  39.     st[i].lazy=-1;
  40.     st[i].c2=st[2*i].c2+st[2*i+1].c2;
  41.     st[i].c5=st[2*i].c5+st[2*i+1].c5;
  42.     st[i].c0=st[2*i].c0+st[2*i+1].c0;
  43. }
  44. void update(int s,int e,int l,int r,int val,int i)
  45. {
  46.     if(st[i].lazy!=-1)
  47.     {
  48.         int x=st[i].lazy;
  49.         int t=0,f=0;
  50.         while(x%2==0&&x)
  51.         {
  52.             x=x/2;
  53.             t++;
  54.         }
  55.         while(x%5==0&&x)
  56.         {
  57.             x=x/5;
  58.             f++;
  59.         }
  60.         st[i].c2=(e-s+1)*t;
  61.         st[i].c5=(e-s+1)*f;
  62.         st[i].c0=(e-s+1)*(st[i].lazy==0);
  63.         if(s!=e)
  64.         {
  65.             st[2*i].lazy=st[i].lazy;
  66.             st[2*i+1].lazy=st[i].lazy;
  67.         }
  68.         st[i].lazy=-1;
  69.     }
  70.     if(e<l||s>r)
  71.         return;
  72.     if(s>=l&&e<=r)
  73.     {
  74.        int x=val;
  75.         int t=0,f=0;
  76.         while(x%2==0&&x)
  77.         {
  78.             x=x/2;
  79.             t++;
  80.         }
  81.         while(x%5==0&&x)
  82.         {
  83.             x=x/5;
  84.             f++;
  85.         }
  86.         st[i].c2=(e-s+1)*t;
  87.         st[i].c5=(e-s+1)*f;
  88.         st[i].c0=(e-s+1)*(val==0);
  89.         if(s!=e)
  90.         {
  91.             st[2*i].lazy=val;
  92.             st[2*i+1].lazy=val;
  93.         }
  94.         return;
  95.     }
  96.     int mid=(s+e)/2;
  97.     update(s,mid,l,r,val,2*i);
  98.     update(mid+1,e,l,r,val,2*i+1);
  99.     st[i].c2=st[2*i].c2+st[2*i+1].c2;
  100.     st[i].c5=st[2*i].c5+st[2*i+1].c5;
  101.     st[i].c0=st[2*i].c0+st[2*i+1].c0;
  102. }
  103. tree query(int s,int e,int l,int r,int i)
  104. {
  105.     if(st[i].lazy!=-1)
  106.     {
  107.         int x=st[i].lazy;
  108.         int t=0,f=0;
  109.         while(x%2==0&&x)
  110.         {
  111.             x=x/2;
  112.             t++;
  113.         }
  114.         while(x%5==0&&x)
  115.         {
  116.             x=x/5;
  117.             f++;
  118.         }
  119.         st[i].c2=(e-s+1)*t;
  120.         st[i].c5=(e-s+1)*f;
  121.         st[i].c0=(e-s+1)*(st[i].lazy==0);
  122.         if(s!=e)
  123.         {
  124.             st[2*i].lazy=st[i].lazy;
  125.             st[2*i+1].lazy=st[i].lazy;
  126.         }
  127.         st[i].lazy=-1;
  128.     }
  129.     if(e<l||s>r)
  130.     {
  131.         tree temp;
  132.         temp.c2=0;
  133.         temp.c5=0;
  134.         temp.c0=0;
  135.         return temp;
  136.     }
  137.     if(s>=l&&e<=r)
  138.     {
  139.         return st[i];
  140.     }
  141.     int mid=(s+e)/2;
  142.     tree temp,le,ri;
  143.     le=query(s,mid,l,r,2*i);
  144.     ri=query(mid+1,e,l,r,2*i+1);
  145.     temp.c2=le.c2+ri.c2;
  146.     temp.c5=le.c5+ri.c5;
  147.     temp.c0=le.c0+ri.c0;
  148.     return temp;
  149. }
  150. int main()
  151. {
  152.     //freopen("input49.txt","r",stdin);
  153.     //freopen("output49.txt","w",stdout);
  154.     int n,i,j,v,l,q;
  155.     scanf("%d",&n);
  156.     for(i=1;i<=n;i++)
  157.     {
  158.         scanf("%d",&a[i]);
  159.     }
  160.     construct(1,n,1);
  161.     cin>>q;
  162.     while(q--)
  163.     {
  164.         scanf("%d",&l);
  165.         if(l)
  166.         {
  167.             scanf("%d %d",&i,&j);
  168.             tree temp;
  169.             temp=query(1,n,i,j,1);
  170.             if(temp.c0)
  171.                 printf("%d\n",1);
  172.             else
  173.                 printf("%d\n",min(temp.c2,temp.c5));
  174.         }
  175.         else
  176.         {
  177.             scanf("%d %d %d",&i,&j,&v);
  178.             update(1,n,i,j,v,1);
  179.         }
  180.     }
  181.     return 0;
  182. }
  183.  
Time limit exceeded #stdin #stdout 5s 10112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WWVkw3
language:
C++ (gcc 8.3)
created:
7 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!