oj.uz

Submission #255602

# Submission time Handle Problem Language Result Execution time Memory
255602 2020-08-01T12:04:01 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 2432 ms 524288 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[400001];
int lazy[400001]={};
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)
        break;
    }
  }
  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)
        break;
    }
  }
  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)
        break;
  }
}
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)
        break;
    }
  }
  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)
        break;
    }
    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)
        break;
  }
}
void init(lli node,lli l,lli r)
{
    while(segt[node].size()!=33)
    {
      segt[node].pb(0);
      if(segt[node].size()>33)
        break;
    }
    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 207 ms 269688 KB Output is correct
2 Correct 208 ms 270244 KB Output is correct
3 Correct 210 ms 269692 KB Output is correct
4 Correct 225 ms 270456 KB Output is correct
5 Correct 240 ms 271224 KB Output is correct
6 Correct 236 ms 271224 KB Output is correct
7 Correct 242 ms 271224 KB Output is correct
8 Correct 238 ms 271228 KB Output is correct
9 Correct 239 ms 271224 KB Output is correct
10 Correct 237 ms 271224 KB Output is correct
11 Correct 256 ms 271352 KB Output is correct
12 Correct 259 ms 271224 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2432 ms 298688 KB Output is correct
2 Correct 1968 ms 290360 KB Output is correct
3 Runtime error 1002 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 273784 KB Output is correct
2 Correct 872 ms 290424 KB Output is correct
3 Correct 963 ms 292600 KB Output is correct
4 Correct 1974 ms 284720 KB Output is correct
5 Runtime error 1171 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 299056 KB Output is correct
2 Correct 2061 ms 299768 KB Output is correct
3 Correct 1458 ms 295152 KB Output is correct
4 Correct 1963 ms 289356 KB Output is correct
5 Runtime error 1151 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -