oj.uz

Submission #255593

# Submission time Handle Problem Language Result Execution time Memory
255593 2020-08-01T11:56:30 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 594 ms 71544 KB 
     #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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 67704 KB Output is correct
2 Correct 58 ms 68092 KB Output is correct
3 Correct 72 ms 67712 KB Output is correct
4 Correct 75 ms 68476 KB Output is correct
5 Correct 92 ms 69240 KB Output is correct
6 Correct 89 ms 69240 KB Output is correct
7 Correct 91 ms 69240 KB Output is correct
8 Correct 88 ms 69240 KB Output is correct
9 Correct 93 ms 69444 KB Output is correct
10 Correct 90 ms 69368 KB Output is correct
11 Correct 89 ms 69240 KB Output is correct
12 Correct 99 ms 69240 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 67704 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 71544 KB Output is correct
2 Runtime error 67 ms 67704 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 67704 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -