oj.uz

Submission #255672

# Submission time Handle Problem Language Result Execution time Memory
255672 2020-08-01T13:57:45 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 602 ms 77432 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;
 
lli n,q,k;
lli segt[400100][34];
lli lazy[400100]={},crazy[400100]={},hi;
lli qu(lli node,lli l,lli r,lli s,lli e)
{
  if(crazy[node]!=0)
  {
    lazy[node]=min(lazy[node]+crazy[node],33*1LL);
    if(l!=r)
    {
    crazy[2*node+1]+=crazy[node];
    crazy[2*node+2]+=crazy[node];
  }
    crazy[node]=0;
  }
  if(r<s||l>e)
    return(0);
  if(l>=s&&r<=e)
  {
    return(segt[node][lazy[node]]);
  }
  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(crazy[node]!=0)
  {
    lazy[node]=min(lazy[node]+crazy[node],33*1LL);
      if(l!=r)
      {
    crazy[2*node+1]+=crazy[node];
    crazy[2*node+2]+=crazy[node];
  }
    crazy[node]=0;
  }
  if(l>e||r<s)
    return;
  if(l>=s&&r<=e)
  {
    lazy[node]=min(lazy[node]+1,33*1LL);
    if(l!=r)
    {
    crazy[2*node+1]=min(crazy[2*node+1]+1,33*1LL);
    crazy[2*node+2]=min(crazy[2*node+2]+1,33*1LL);
  }
    return;
  }
  lli m=(l+r)/2;
  up2(2*node+1,l,m,s,e);
  up2(2*node+2,m+1,r,s,e);
  lazy[node]=0;
  for(int i=0;i<34;++i)
    segt[node][i]=segt[2*node+1][min(lazy[2*node+1]+i,33*1LL)]+segt[2*node+2][min(lazy[2*node+2]+i,33*1LL)];
}
lli c=0;
void up1(lli node,lli l,lli r,lli in,lli v)
{
  
  if(crazy[node]!=0)
  {
    lazy[node]=min(lazy[node]+crazy[node],33*1LL);
      if(l!=r)
      {
    crazy[2*node+1]+=crazy[node];
    crazy[2*node+2]+=crazy[node];
  }
   crazy[node]=0;
  }
  if(l==r)
  {
    lazy[node]=0;
    crazy[node]=0;
    for(int i=0;i<34*1LL;++i)
    {
      segt[node][i]=(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);
  lazy[node]=0;
  crazy[node]=0;
  qu(2*node+1,l,m,l,m);
  qu(2*node+2,m+1,r,m+1,r);
  for(int i=0;i<34;++i)
    segt[node][i]=segt[2*node+1][min(lazy[2*node+1]+i,33*1LL)]+segt[2*node+2][min(lazy[2*node+2]+i,33*1LL)];
}
void init(lli node,lli l,lli r)
{
    for(int i=0;i<33;++i)
      segt[node][i]=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);
  }
  int c=0;
  for(lli i=0;i<q;++i)
  {
    lli f,s,t;
    cin>>f>>s>>t;
    hi=i;
    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--;
      c++;
      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 5 ms 512 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 9 ms 1536 KB Output is correct
5 Correct 11 ms 2688 KB Output is correct
6 Correct 12 ms 2688 KB Output is correct
7 Correct 11 ms 2688 KB Output is correct
8 Correct 12 ms 2688 KB Output is correct
9 Correct 12 ms 2688 KB Output is correct
10 Correct 12 ms 2688 KB Output is correct
11 Correct 11 ms 2688 KB Output is correct
12 Correct 11 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 38008 KB Output is correct
2 Correct 316 ms 22220 KB Output is correct
3 Correct 370 ms 74744 KB Output is correct
4 Correct 460 ms 76920 KB Output is correct
5 Correct 579 ms 77432 KB Output is correct
6 Correct 538 ms 77432 KB Output is correct
7 Correct 602 ms 77304 KB Output is correct
8 Correct 600 ms 77176 KB Output is correct
9 Correct 490 ms 77176 KB Output is correct
10 Correct 513 ms 77048 KB Output is correct
11 Correct 485 ms 77048 KB Output is correct
12 Correct 487 ms 77048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 5112 KB Output is correct
2 Correct 136 ms 37368 KB Output is correct
3 Correct 163 ms 37496 KB Output is correct
4 Correct 298 ms 19320 KB Output is correct
5 Correct 500 ms 74612 KB Output is correct
6 Correct 516 ms 75896 KB Output is correct
7 Correct 516 ms 76024 KB Output is correct
8 Correct 511 ms 75896 KB Output is correct
9 Correct 478 ms 75608 KB Output is correct
10 Correct 480 ms 75640 KB Output is correct
11 Correct 463 ms 75588 KB Output is correct
12 Correct 454 ms 75512 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 37792 KB Output is correct
2 Correct 344 ms 37604 KB Output is correct
3 Correct 251 ms 37496 KB Output is correct
4 Correct 349 ms 19272 KB Output is correct
5 Correct 552 ms 75000 KB Output is correct
6 Correct 524 ms 76920 KB Output is correct
7 Correct 526 ms 77048 KB Output is correct
8 Correct 527 ms 77176 KB Output is correct
9 Correct 493 ms 76920 KB Output is correct
10 Correct 466 ms 77048 KB Output is correct
11 Correct 463 ms 76920 KB Output is correct
12 Correct 469 ms 76924 KB Output is correct