oj.uz

Submission #255651

# Submission time Handle Problem Language Result Execution time Memory
255651 2020-08-01T13:32:42 Z uacoder123 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 380 ms 39700 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[100001]={};
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;
  crazy[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)
  {
    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 8 ms 1664 KB Output is correct
5 Correct 12 ms 2816 KB Output is correct
6 Correct 13 ms 2816 KB Output is correct
7 Correct 12 ms 2816 KB Output is correct
8 Correct 12 ms 2856 KB Output is correct
9 Correct 19 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 11 ms 2816 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 380 ms 39700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5540 KB Output is correct
2 Correct 150 ms 37652 KB Output is correct
3 Incorrect 163 ms 37624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 298 ms 39032 KB Output isn't correct
2 Halted 0 ms 0 KB -