oj.uz

Submission #31840

# Submission time Handle Problem Language Result Execution time Memory
31840 2017-09-11T03:51:57 Z Kanvie Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 746 ms 9048 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
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 dolazy(int k,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;
    }
    return;
}
void upd(int k, int l, int r, int p, int gt)
{
    dolazy(k,l,r);
    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;
    dolazy(k,l,r);
    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)
{
    dolazy(k,l,r);
    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);
}
signed 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 13 ms 9048 KB Output is correct
3 Correct 0 ms 9048 KB Output is correct
4 Correct 23 ms 9048 KB Output is correct
5 Correct 9 ms 9048 KB Output is correct
6 Correct 23 ms 9048 KB Output is correct
7 Correct 16 ms 9048 KB Output is correct
8 Correct 9 ms 9048 KB Output is correct
9 Correct 13 ms 9048 KB Output is correct
10 Correct 9 ms 9048 KB Output is correct
11 Correct 16 ms 9048 KB Output is correct
12 Correct 13 ms 9048 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 9048 KB Output is correct
2 Correct 166 ms 9048 KB Output is correct
3 Correct 203 ms 9048 KB Output is correct
4 Correct 429 ms 9048 KB Output is correct
5 Correct 233 ms 9048 KB Output is correct
6 Correct 366 ms 9048 KB Output is correct
7 Correct 309 ms 9048 KB Output is correct
8 Correct 366 ms 9048 KB Output is correct
9 Correct 213 ms 9048 KB Output is correct
10 Correct 336 ms 9048 KB Output is correct
11 Correct 186 ms 9048 KB Output is correct
12 Correct 259 ms 9048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9048 KB Output is correct
2 Correct 53 ms 9048 KB Output is correct
3 Correct 69 ms 9048 KB Output is correct
4 Correct 269 ms 9048 KB Output is correct
5 Correct 529 ms 9048 KB Output is correct
6 Correct 279 ms 9048 KB Output is correct
7 Correct 413 ms 9048 KB Output is correct
8 Correct 263 ms 9048 KB Output is correct
9 Correct 326 ms 9048 KB Output is correct
10 Correct 409 ms 9048 KB Output is correct
11 Correct 426 ms 9048 KB Output is correct
12 Correct 249 ms 9048 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 9048 KB Output is correct
2 Correct 489 ms 9048 KB Output is correct
3 Correct 343 ms 9048 KB Output is correct
4 Correct 599 ms 9048 KB Output is correct
5 Correct 613 ms 9048 KB Output is correct
6 Correct 743 ms 9048 KB Output is correct
7 Correct 506 ms 9048 KB Output is correct
8 Correct 549 ms 9048 KB Output is correct
9 Correct 603 ms 9048 KB Output is correct
10 Correct 746 ms 9048 KB Output is correct
11 Correct 583 ms 9048 KB Output is correct
12 Correct 733 ms 9048 KB Output is correct