oj.uz

Submission #565999

# Submission time Handle Problem Language Result Execution time Memory
565999 2022-05-21T16:12:40 Z groshi Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 224 ms 2404 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)
            {
                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 4 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 4 ms 360 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 50 ms 1504 KB Output is correct
2 Correct 60 ms 1200 KB Output is correct
3 Correct 44 ms 1740 KB Output is correct
4 Correct 56 ms 2216 KB Output is correct
5 Correct 66 ms 2316 KB Output is correct
6 Correct 63 ms 2376 KB Output is correct
7 Correct 69 ms 2376 KB Output is correct
8 Correct 66 ms 2356 KB Output is correct
9 Correct 61 ms 2404 KB Output is correct
10 Correct 65 ms 2356 KB Output is correct
11 Correct 66 ms 2380 KB Output is correct
12 Correct 62 ms 2348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 452 KB Output is correct
2 Correct 15 ms 980 KB Output is correct
3 Correct 21 ms 980 KB Output is correct
4 Correct 45 ms 780 KB Output is correct
5 Correct 63 ms 1876 KB Output is correct
6 Correct 72 ms 1944 KB Output is correct
7 Correct 58 ms 1996 KB Output is correct
8 Correct 66 ms 1968 KB Output is correct
9 Correct 63 ms 1872 KB Output is correct
10 Correct 62 ms 2064 KB Output is correct
11 Correct 60 ms 1912 KB Output is correct
12 Correct 64 ms 1968 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 1228 KB Output is correct
2 Correct 84 ms 1316 KB Output is correct
3 Correct 103 ms 1168 KB Output is correct
4 Correct 103 ms 1076 KB Output is correct
5 Correct 126 ms 2176 KB Output is correct
6 Correct 138 ms 2176 KB Output is correct
7 Correct 124 ms 2380 KB Output is correct
8 Correct 165 ms 2164 KB Output is correct
9 Correct 157 ms 2200 KB Output is correct
10 Correct 180 ms 2240 KB Output is correct
11 Correct 137 ms 2260 KB Output is correct
12 Correct 224 ms 2252 KB Output is correct