oj.uz

Submission #31832

# Submission time Handle Problem Language Result Execution time Memory
31832 2017-09-11T03:34:27 Z Kanvie Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 5920 KB 
#include<bits/stdc++.h>
using namespace std;
int n,kk,q,x,y,z;
long long f[400001],a[100001];
void init(int k, int l, int r)
{
    if(r<l)return;
    if(l==r)
    {
        f[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    init(2*k,l,mid);
    init(2*k+1,mid+1,r);
    f[k]=f[2*k]+f[2*k+1];
}
void upd(int k, int l, int r, int p, int gt)
{
    if(p<l||p>r||l>r)return;
    if(l==r)
    {
        f[k]=gt;
        return;
    }
    int mid=(l+r)/2;
    upd(2*k,l,mid,p,gt);
    upd(2*k+1,mid+1,r,p,gt);
    f[k]=f[2*k]+f[2*k+1];
}
void chg(int k, int l, int r, int L, int R)
{
    if(R<l||L>r||l>r)return;
    if(l==r)
    {
        f[k]/=kk;
        return;
    }
    int mid=(l+r)/2;
    chg(2*k,l,mid,L,R);
    chg(2*k+1,mid+1,r,L,R);
    f[k]=f[2*k]+f[2*k+1];
}
long long gets(int k, int l, int r, int L, int R)
{
    if(R<l||L>r||l>r)return 0;
    if(L<=l&&r<=R)return f[k];
    int mid=(l+r)/2;
    return gets(2*k,l,mid,L,R)+gets(2*k+1,mid+1,r,L,R);
}
int main()
{
    cin>>n>>q>>kk;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    init(1,1,n);
    while(q--)
    {
        cin>>x>>y>>z;
        if(x==1)
            upd(1,1,n,y,z);
        else
        {
            if(x==2)
                chg(1,1,n,y,z);
            else
                cout<<gets(1,1,n,y,z)<<"\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5920 KB Output is correct
2 Correct 6 ms 5920 KB Output is correct
3 Correct 3 ms 5920 KB Output is correct
4 Correct 19 ms 5920 KB Output is correct
5 Correct 26 ms 5920 KB Output is correct
6 Correct 23 ms 5920 KB Output is correct
7 Correct 26 ms 5920 KB Output is correct
8 Correct 13 ms 5920 KB Output is correct
9 Correct 33 ms 5920 KB Output is correct
10 Correct 26 ms 5920 KB Output is correct
11 Correct 23 ms 5920 KB Output is correct
12 Correct 19 ms 5920 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 0 KB -1: Interrupted system call
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 5920 KB Output is correct
2 Correct 1419 ms 5920 KB Output is correct
3 Correct 2249 ms 5920 KB Output is correct
4 Execution timed out 5000 ms 5920 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 0 KB -1: Interrupted system call
2 Halted 0 ms 0 KB -