oj.uz

Submission #565998

# Submission time Handle Problem Language Result Execution time Memory
565998 2022-05-21T16:11:42 Z groshi Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 243 ms 5964 KB 
#include<iostream>

using namespace std;
int k;
long long drzewo[3000000];
int maxx[3000000];
int pot=1;
long long zap(int x,int l,int r,int a,int b)
{
    if(r<a || l>b)
        return 0;
    if(l>=a && r<=b)
        return drzewo[x];
    int mid=(l+r)/2;
    return zap(x*2,l,mid,a,b)+zap(x*2+1,mid+1,r,a,b);
}
void add(int x,int l,int r,int a,int b)
{
    if(r<a || l>a)
        return;
    if(l==r)
    {
        drzewo[x]=b;
        maxx[x]=b;
        return;
    }
    int mid=(l+r)/2;
    add(x*2,l,mid,a,b);
    add(x*2+1,mid+1,r,a,b);
    drzewo[x]=drzewo[x*2]+drzewo[x*2+1];
    maxx[x]=max(maxx[x*2],maxx[x*2+1]);
}
void spray(int x,int l,int r,int a,int b)
{
    if(l>b || r<a)
        return;
    if(maxx[x]==0)
        return;
    if(l==r)
    {
        drzewo[x]/=k;
        maxx[x]/=k;
        return;
    }
    int mid=(l+r)/2;
    spray(x*2,l,mid,a,b);
    spray(x*2+1,mid+1,r,a,b);
    drzewo[x]=drzewo[x*2]+drzewo[x*2+1];
    maxx[x]=max(maxx[x*2],maxx[x*2+1]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,x;
    cin>>n>>q>>k;
    while(pot<=n)
        pot*=2;
    pot--;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        drzewo[i+pot]=x;
        maxx[i+pot]=x;
    }
    for(int i=pot;i>=1;i--)
        drzewo[i]=drzewo[i*2]+drzewo[i*2+1];
    for(int i=pot;i>=1;i--)
        maxx[i]=max(maxx[i*2],maxx[i*2+1]);
    while(q--)
    {
        int x,a,b;
        cin>>x>>a>>b;
        if(x==1)
            add(1,pot+1,pot*2+1,a+pot,b);
        if(x==2)
        {
            if(k==1)
                continue;
            spray(1,pot+1,pot*2+1,a+pot,b+pot);
        }
        if(x==3)
            cout<<zap(1,pot+1,pot*2+1,a+pot,b+pot)<<"\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2104 KB Output is correct
2 Correct 41 ms 1856 KB Output is correct
3 Correct 32 ms 3028 KB Output is correct
4 Correct 43 ms 3328 KB Output is correct
5 Correct 54 ms 5876 KB Output is correct
6 Correct 53 ms 5944 KB Output is correct
7 Correct 57 ms 5916 KB Output is correct
8 Correct 63 ms 5912 KB Output is correct
9 Correct 52 ms 5816 KB Output is correct
10 Correct 54 ms 5748 KB Output is correct
11 Correct 49 ms 5964 KB Output is correct
12 Correct 55 ms 5732 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 516 KB Output is correct
2 Correct 10 ms 1620 KB Output is correct
3 Correct 14 ms 1620 KB Output is correct
4 Correct 46 ms 1028 KB Output is correct
5 Correct 54 ms 3092 KB Output is correct
6 Correct 50 ms 3028 KB Output is correct
7 Correct 48 ms 3464 KB Output is correct
8 Correct 52 ms 4468 KB Output is correct
9 Correct 48 ms 4332 KB Output is correct
10 Correct 54 ms 4324 KB Output is correct
11 Correct 61 ms 4348 KB Output is correct
12 Correct 48 ms 4364 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1868 KB Output is correct
2 Correct 84 ms 1868 KB Output is correct
3 Correct 106 ms 1740 KB Output is correct
4 Correct 113 ms 1364 KB Output is correct
5 Correct 118 ms 3304 KB Output is correct
6 Correct 147 ms 3276 KB Output is correct
7 Correct 123 ms 3256 KB Output is correct
8 Correct 178 ms 3268 KB Output is correct
9 Correct 163 ms 3316 KB Output is correct
10 Correct 192 ms 3444 KB Output is correct
11 Correct 131 ms 3276 KB Output is correct
12 Correct 243 ms 3316 KB Output is correct