oj.uz

Submission #255586

# Submission time Handle Problem Language Result Execution time Memory
255586 2020-08-01T11:49:07 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 573 ms 71812 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(segt[node].size()>33)
        exit(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(segt[node].size()>33)
        exit(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()));
    if(segt[node].size()>33)
        exit(1);
  }
}
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(segt[node].size()>33)
        exit(1);
    }
  }
  if(l==r)
  {
    lazy[node]=0;
    segt[node].clear();
    while(segt[node].size()!=33)
    {
      segt[node].pb(v);
      v/=k;
      if(segt[node].size()>33)
        exit(1);
    }
    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()));
    if(segt[node].size()>33)
        exit(1);
  }
}
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 61 ms 67704 KB Output is correct
2 Correct 71 ms 68088 KB Output is correct
3 Correct 63 ms 67712 KB Output is correct
4 Correct 78 ms 68472 KB Output is correct
5 Correct 101 ms 69368 KB Output is correct
6 Correct 94 ms 69496 KB Output is correct
7 Correct 102 ms 69376 KB Output is correct
8 Correct 90 ms 69240 KB Output is correct
9 Correct 93 ms 69368 KB Output is correct
10 Correct 94 ms 69496 KB Output is correct
11 Correct 107 ms 69240 KB Output is correct
12 Correct 106 ms 69240 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 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 573 ms 71812 KB Output is correct
2 Runtime error 69 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 69 ms 67704 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -