Submission #255593

#	Time	Username	Problem	Language	Result	Execution time	Memory
255593		uacoder123	Sterilizing Spray (JOI15_sterilizing)	C++14	5 / 100	594 ms	71544 KiB

sterilizing

     #include <bits/stdc++.h>
    using namespace std;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) int(x.size())
    #define mp(i,a) make_pair(i,a)
    #define pb(a) push_back(a)
    #define bit(x,b) (x&(1LL<<b))
     
    typedef long long int lli;
    typedef pair <lli,lli> ii;
    typedef pair <lli,ii> iii;
    typedef vector <lli> vi;
     
    int n,q,k;
    deque<lli> segt[100001];
    int lazy[100001]={};
    lli qu(lli node,lli l,lli r,lli s,lli e)
    {
      if(r<s||l>e)
        return(0);
      if(lazy[node]!=0)
      {
        lazy[2*node+1]=min(lazy[2*node+1]+lazy[node],33);
        lazy[2*node+2]=min(lazy[2*node+2]+lazy[node],33);
        while(lazy[node]!=0)
        {
          if(k==1)
            segt[node].pb(segt[node].front());
          else
            segt[node].pb(0);
          segt[node].pop_front();
          lazy[node]-=1;
          
        }
      }
      if(l>=s&&r<=e)
        return(segt[node].front());
      lli m=(l+r)/2;
      lli q1=qu(2*node+1,l,m,s,e),q2=qu(2*node+2,m+1,r,s,e);
      return(q1+q2);
    }
    void up2(lli node,lli l,lli r,lli s,lli e)
    {
      if(l>e||r<s)
        return;
      if(lazy[node]!=0)
      {
        lazy[2*node+1]=min(lazy[2*node+1]+lazy[node],33);
        lazy[2*node+2]=min(lazy[2*node+2]+lazy[node],33);
        while(lazy[node]!=0)
        {
          if(k==1)
            segt[node].pb(segt[node].front());
          else
            segt[node].pb(0);
          segt[node].pop_front();
          lazy[node]-=1;
          
        }
      }
      if(l>=s&&r<=e)
      {
        if(k==1)
            segt[node].pb(segt[node].front());
          else
            segt[node].pb(0);
        segt[node].pop_front();
        lazy[2*node+1]=min(lazy[2*node+1]+1,33);
        lazy[2*node+2]=min(lazy[2*node+2]+1,33);
        return;
      }
      lli m=(l+r)/2;
      up2(2*node+1,l,m,s,e);
      up2(2*node+2,m+1,r,s,e);
      segt[node].clear();
      qu(2*node+1,l,m,l,m);
      qu(2*node+2,m+1,r,m+1,r);
      while(segt[node].size()!=33)
      {
        segt[node].pb(segt[2*node+1].at(segt[node].size())+segt[2*node+2].at(segt[node].size()));
        
      }
    }
    void up1(lli node,lli l,lli r,lli in,lli v)
    {
      if(lazy[node]!=0)
      {
        lazy[2*node+1]=min(lazy[2*node+1]+lazy[node],33);
        lazy[2*node+2]=min(lazy[2*node+2]+lazy[node],33);
        while(lazy[node]!=0)
        {
          if(k==1)
            segt[node].pb(segt[node].front());
          else
            segt[node].pb(0);
          segt[node].pop_front();
          lazy[node]-=1;
          
        }
      }
      if(l==r)
      {
        lazy[node]=0;
        segt[node].clear();
        while(segt[node].size()!=33)
        {
          segt[node].pb(v);
          v/=k;
          
        }
        return;
      }
      lli m=(l+r)/2;
      if(in<=m)
        up1(2*node+1,l,m,in,v);
      else
        up1(2*node+2,m+1,r,in,v);
      segt[node].clear();
      qu(2*node+1,l,m,l,m);
      qu(2*node+2,m+1,r,m+1,r);
      while(segt[node].size()!=33)
      {
        segt[node].pb(segt[2*node+1].at(segt[node].size())+segt[2*node+2].at(segt[node].size()));
        
      }
    }
    void init(lli node,lli l,lli r)
    {
        while(segt[node].size()!=33)
        {
          segt[node].pb(0);
          if(segt[node].size()>33)
            exit(1);
        }
        lli m=(l+r)/2;
        if(l!=r)
        {
          init(2*node+1,l,m);
          init(2*node+2,m+1,r);
        }
    }
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      cin>>n>>q>>k;
      init(0,0,n-1);
      for(lli i=0;i<n;++i)
      {
        lli f;
        cin>>f;
        up1(0,0,n-1,i,f);
      }
      for(lli i=0;i<q;++i)
      {
        lli f,s,t;
        cin>>f>>s>>t;
        if(f==1)
        {
          s--;
          up1(0,0,n-1,s,t);
        }
        else if(f==2)
        {
          s--;
          t--;
          up2(0,0,n-1,s,t);
        }
        else
        {
          s--;
          t--;
          cout<<qu(0,0,n-1,s,t)<<endl;
        }
      }
      return(0);
    }

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75