oj.uz

Submission #31836

# Submission time Handle Problem Language Result Execution time Memory
31836 2017-09-11T03:47:07 Z Kanvie Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 329 ms 7484 KB 
#include<bits/stdc++.h>
using namespace std;
int n,kk,q,x,y,z,mx[400001];
long long f[400001],a[100001];
void init(int k, int l, int r)
{
    if(r<l)return;
    if(l==r)
    {
        f[k]=a[l];
        mx[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    init(2*k,l,mid);
    init(2*k+1,mid+1,r);
    f[k]=f[2*k]+f[2*k+1];
    mx[k]=max(mx[2*k],mx[2*k+1]);
}
void upd(int k, int l, int r, int p, int gt)
{
    if(p<l||p>r||l>r)return;
    if(l==r)
    {
        f[k]=gt;
        mx[k]=gt;
        return;
    }
    int mid=(l+r)/2;
    upd(2*k,l,mid,p,gt);
    upd(2*k+1,mid+1,r,p,gt);
    f[k]=f[2*k]+f[2*k+1];
    mx[k]=max(mx[2*k],mx[2*k+1]);
}
void chg(int k, int l, int r, int L, int R)
{
    if(kk==1)return;
    if(l!=r&&mx[k]==0)
    {
        mx[2*k]=0;
        mx[2*k+1]=0;
        f[2*k]=0;
        f[2*k+1]=0;
    }
    if(R<l||L>r||l>r)return;
    if(L<=l&&r<=R&&mx[k]<kk)
    {
        f[k]=0;
        mx[k]=0;
        return;
    }
    if(l==r)
    {
        f[k]/=kk;
        mx[k]=f[k];
        return;
    }
    int mid=(l+r)/2;
    chg(2*k,l,mid,L,R);
    chg(2*k+1,mid+1,r,L,R);
    f[k]=f[2*k]+f[2*k+1];
    mx[k]=max(mx[2*k],mx[2*k+1]);
}
long long gets(int k, int l, int r, int L, int R)
{
    if(l!=r&&mx[k]==0)
    {
        mx[2*k]=0;
        mx[2*k+1]=0;
        f[2*k]=0;
        f[2*k+1]=0;
    }
    if(R<l||L>r||l>r)return 0;
    if(L<=l&&r<=R)return f[k];
    int mid=(l+r)/2;
    return gets(2*k,l,mid,L,R)+gets(2*k+1,mid+1,r,L,R);
}
int main()
{
    cin>>n>>q>>kk;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    init(1,1,n);
    while(q--)
    {
        cin>>x>>y>>z;
        if(x==1)
            upd(1,1,n,y,z);
        else
        {
            if(x==2)
                chg(1,1,n,y,z);
            else
                cout<<gets(1,1,n,y,z)<<"\n";
        }
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 7484 KB Output is correct
2 Correct 259 ms 7484 KB Output is correct
3 Correct 163 ms 7484 KB Output is correct
4 Correct 189 ms 7484 KB Output is correct
5 Correct 326 ms 7484 KB Output is correct
6 Correct 313 ms 7484 KB Output is correct
7 Correct 209 ms 7484 KB Output is correct
8 Correct 329 ms 7484 KB Output is correct
9 Correct 169 ms 7484 KB Output is correct
10 Correct 193 ms 7484 KB Output is correct
11 Correct 216 ms 7484 KB Output is correct
12 Correct 276 ms 7484 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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