oj.uz

Submission #565995

# Submission time Handle Problem Language Result Execution time Memory
565995 2022-05-21T16:08:55 Z groshi Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 3328 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)
            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 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 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 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 2152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 508 KB Output is correct
2 Correct 10 ms 1592 KB Output is correct
3 Correct 15 ms 1636 KB Output is correct
4 Correct 43 ms 1028 KB Output is correct
5 Correct 52 ms 3064 KB Output is correct
6 Correct 51 ms 3028 KB Output is correct
7 Execution timed out 5060 ms 3156 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1864 KB Output is correct
2 Correct 84 ms 1948 KB Output is correct
3 Correct 107 ms 1764 KB Output is correct
4 Correct 110 ms 1380 KB Output is correct
5 Correct 128 ms 3312 KB Output is correct
6 Correct 143 ms 3296 KB Output is correct
7 Correct 116 ms 3276 KB Output is correct
8 Correct 210 ms 3308 KB Output is correct
9 Correct 153 ms 3276 KB Output is correct
10 Correct 178 ms 3328 KB Output is correct
11 Correct 129 ms 3276 KB Output is correct
12 Correct 238 ms 3324 KB Output is correct