oj.uz

Submission #954404

# Submission time Handle Problem Language Result Execution time Memory
954404 2024-03-27T19:35:39 Z ziyad_alharbi Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 6312 KB 
#include <bits/stdc++.h>
using namespace std;
vector<long long>sg,a(100005);
int n,sz;
void is()
{
    for(sz=1;sz<n;sz*=2);
    sg.resize(sz*2,0);
}
void up(int i,long long v)
{
    i+=sz;
    sg[i]=v;
    for(i/=2;i>0;i/=2)
    {
        sg[i]=sg[i*2]+sg[i*2+1];
    }
}
long long q(int v,int lw,int h,int l,int r)
{
    if(lw<=l&&r<=h)return sg[v];
    else if(l>=h||lw>=r)return 0;
    else
    {
        int m=(l+r)/2;
        return q(v*2,lw,h,l,m)+q(v*2+1,lw,h,m,r);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        int qr,k;
        cin>>n>>qr>>k;
        is();
        for(int x=0;x<n;x++)
        {
            cin>>a[x];
            up(x,a[x]);
        }
        
        if(k==1)
        {
            while(qr--)
            {
                int t,l,r;
                cin>>t>>l>>r;
                if(t==1)up(l-1,r);
                if(t==3)cout<<q(1,l-1,r,0,sz)<<'\n';
            }
        }
        else
        {
            while(qr--)
            {
                int t,l,r;
                cin>>t>>l>>r;
                if(t==1)a[l-1]=r;
                if(t==2)
                {
                    for(int x=l-1;x<r;x++)a[x]/=k;
                }
                if(t==3)
                {
                    long long s=0;
                    for(int x=l-1;x<r;x++)s+=a[x];
                    cout<<s<<'\n';
                }
            }
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2652 KB Output is correct
2 Correct 30 ms 4220 KB Output is correct
3 Correct 28 ms 5212 KB Output is correct
4 Correct 36 ms 5716 KB Output is correct
5 Correct 42 ms 5976 KB Output is correct
6 Correct 43 ms 5972 KB Output is correct
7 Correct 49 ms 6312 KB Output is correct
8 Correct 44 ms 5972 KB Output is correct
9 Correct 41 ms 5972 KB Output is correct
10 Correct 39 ms 5968 KB Output is correct
11 Correct 39 ms 5968 KB Output is correct
12 Correct 46 ms 5964 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 1368 KB Output is correct
2 Correct 275 ms 2260 KB Output is correct
3 Correct 439 ms 2268 KB Output is correct
4 Correct 955 ms 1800 KB Output is correct
5 Correct 3964 ms 3840 KB Output is correct
6 Correct 3939 ms 3588 KB Output is correct
7 Correct 36 ms 3408 KB Output is correct
8 Correct 3993 ms 4900 KB Output is correct
9 Execution timed out 5023 ms 3924 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1434 ms 2560 KB Output is correct
2 Correct 1662 ms 2528 KB Output is correct
3 Correct 886 ms 2404 KB Output is correct
4 Correct 1224 ms 2204 KB Output is correct
5 Correct 3977 ms 3760 KB Output is correct
6 Correct 3999 ms 4008 KB Output is correct
7 Correct 4016 ms 3748 KB Output is correct
8 Correct 3956 ms 3932 KB Output is correct
9 Execution timed out 5053 ms 4108 KB Time limit exceeded
10 Halted 0 ms 0 KB -