oj.uz

Submission #255584

# Submission time Handle Problem Language Result Execution time Memory
255584 2020-08-01T11:44:05 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 559 ms 136952 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);
    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 59 ms 67704 KB Output is correct
2 Correct 58 ms 68088 KB Output is correct
3 Correct 58 ms 67704 KB Output is correct
4 Correct 75 ms 68484 KB Output is correct
5 Correct 101 ms 69368 KB Output is correct
6 Correct 98 ms 69368 KB Output is correct
7 Correct 108 ms 69240 KB Output is correct
8 Correct 103 ms 69368 KB Output is correct
9 Correct 103 ms 69344 KB Output is correct
10 Correct 95 ms 69368 KB Output is correct
11 Correct 103 ms 69368 KB Output is correct
12 Correct 105 ms 69240 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 136952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 71672 KB Output is correct
2 Runtime error 118 ms 136848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 136824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -