oj.uz

Submission #255599

# Submission time Handle Problem Language Result Execution time Memory
255599 2020-08-01T11:59:51 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 616 ms 136972 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)
        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 66 ms 67720 KB Output is correct
2 Correct 61 ms 68120 KB Output is correct
3 Correct 65 ms 67696 KB Output is correct
4 Correct 82 ms 68412 KB Output is correct
5 Correct 103 ms 69284 KB Output is correct
6 Correct 103 ms 69372 KB Output is correct
7 Correct 99 ms 69244 KB Output is correct
8 Correct 107 ms 69312 KB Output is correct
9 Correct 95 ms 69368 KB Output is correct
10 Correct 103 ms 69368 KB Output is correct
11 Correct 118 ms 69368 KB Output is correct
12 Correct 101 ms 69240 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 136972 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 616 ms 71800 KB Output is correct
2 Runtime error 139 ms 136964 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 134 ms 136824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -