oj.uz

Submission #565985

# Submission time Handle Problem Language Result Execution time Memory
565985 2022-05-21T16:02:31 Z groshi Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 4640 KB 
#include<iostream>

using namespace std;
int k;
long long drzewo[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;
        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];
}
void spray(int x,int l,int r,int a,int b)
{
    if(l>b || r<a)
        return;
    if(drzewo[x]==0)
        return;
    if(l==r)
    {
        drzewo[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];
}
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;
        add(1,pot+1,pot*2+1,i+pot,x);
    }
    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 2 ms 344 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 5 ms 424 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 4 ms 432 KB Output is correct
9 Correct 4 ms 424 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 468 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4448 ms 3372 KB Output is correct
2 Correct 3033 ms 2892 KB Output is correct
3 Correct 4561 ms 3576 KB Output is correct
4 Execution timed out 5010 ms 4260 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 852 KB Output is correct
2 Correct 16 ms 1236 KB Output is correct
3 Correct 21 ms 1364 KB Output is correct
4 Correct 48 ms 1932 KB Output is correct
5 Correct 71 ms 3304 KB Output is correct
6 Correct 66 ms 3320 KB Output is correct
7 Execution timed out 5034 ms 3008 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2896 KB Output is correct
2 Correct 90 ms 3032 KB Output is correct
3 Correct 115 ms 2324 KB Output is correct
4 Correct 115 ms 2784 KB Output is correct
5 Correct 138 ms 4640 KB Output is correct
6 Correct 153 ms 4624 KB Output is correct
7 Correct 128 ms 4636 KB Output is correct
8 Correct 189 ms 4576 KB Output is correct
9 Correct 166 ms 4532 KB Output is correct
10 Correct 191 ms 4428 KB Output is correct
11 Correct 161 ms 4480 KB Output is correct
12 Correct 245 ms 4576 KB Output is correct