oj.uz

Submission #255668

# Submission time Handle Problem Language Result Execution time Memory
255668 2020-08-01T13:47:29 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 546 ms 78072 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[400001][34];
lli lazy[400001]={},crazy[400001]={},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);
    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);
    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);
    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);
    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)
  {
    hi=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;
    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 4 ms 1024 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 12 ms 2816 KB Output is correct
6 Correct 12 ms 2816 KB Output is correct
7 Correct 12 ms 2816 KB Output is correct
8 Correct 12 ms 2816 KB Output is correct
9 Correct 13 ms 2816 KB Output is correct
10 Correct 12 ms 2816 KB Output is correct
11 Correct 12 ms 2816 KB Output is correct
12 Correct 19 ms 2816 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 39288 KB Output is correct
2 Correct 312 ms 24952 KB Output is correct
3 Incorrect 369 ms 77432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5624 KB Output is correct
2 Correct 141 ms 38648 KB Output is correct
3 Correct 165 ms 38776 KB Output is correct
4 Correct 316 ms 20600 KB Output is correct
5 Incorrect 546 ms 76920 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 39032 KB Output is correct
2 Correct 344 ms 40184 KB Output is correct
3 Correct 233 ms 39544 KB Output is correct
4 Correct 330 ms 21368 KB Output is correct
5 Incorrect 517 ms 78072 KB Output isn't correct
6 Halted 0 ms 0 KB -