oj.uz

Submission #565989

# Submission time Handle Problem Language Result Execution time Memory
565989 2022-05-21T16:04:23 Z groshi Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 2572 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;
        drzewo[i+pot]=x;
    }
    for(int i=pot;i>=1;i--)
        drzewo[i]=drzewo[i*2]+drzewo[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 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 336 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 3 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4437 ms 1744 KB Output is correct
2 Correct 2697 ms 1608 KB Output is correct
3 Correct 4351 ms 2476 KB Output is correct
4 Execution timed out 5066 ms 2572 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Correct 11 ms 1192 KB Output is correct
3 Correct 15 ms 1108 KB Output is correct
4 Correct 42 ms 796 KB Output is correct
5 Correct 51 ms 2292 KB Output is correct
6 Correct 50 ms 2148 KB Output is correct
7 Execution timed out 5063 ms 2468 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1336 KB Output is correct
2 Correct 80 ms 1420 KB Output is correct
3 Correct 89 ms 1236 KB Output is correct
4 Correct 107 ms 1052 KB Output is correct
5 Correct 109 ms 2304 KB Output is correct
6 Correct 123 ms 2384 KB Output is correct
7 Correct 123 ms 2424 KB Output is correct
8 Correct 149 ms 2408 KB Output is correct
9 Correct 141 ms 2416 KB Output is correct
10 Correct 153 ms 2428 KB Output is correct
11 Correct 118 ms 2424 KB Output is correct
12 Correct 208 ms 2504 KB Output is correct