Submission #558822

#	Time	Username	Problem	Language	Result	Execution time	Memory
558822		NintsiChkhaidze	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	244 ms	7364 KiB

sterilizing

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define int ll
#define s second
#define f first
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 100005;
int k,mx[4*N],sum[4*N];

void upd(int h,int l,int r,int idx,int val){
    if (l==r){
        sum[h] = val;
        mx[h] = val;
        return;
    } 
    if (idx > (l+r)/2) upd(right,idx,val);
    else upd(left,idx,val);
    
    sum[h] = sum[h*2] + sum[h*2+1];
    mx[h] = max(mx[h*2],mx[h*2+1]);
}
void updseg(int h,int l,int r,int L,int R){
    if (r < L || R < l || mx[h] == 0) return;
    if (l == r){
        sum[h] /= k;
        mx[h] = sum[h];
        return;
    }
    updseg(left,L,R);
    updseg(right,L,R);
    sum[h] = sum[h*2] + sum[h*2+1];
    mx[h] = max(mx[h*2],mx[h*2+1]);
}
int getsum(int h,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return sum[h];
    return getsum(left,L,R) + getsum(right,L,R);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,t;
    cin>>n>>t>>k;
    for (int i=1;i<=n;i++){
        int a;
        cin>>a;
        upd(1,1,n,i,a);
    }
    
    while(t--){
        int tp,l,r;
        cin>>tp>>l>>r;
        if (tp == 1) {
            upd(1,1,n,l,r);
        }else if (tp == 2){
            if (k > 1) updseg(1,1,n,l,r);
        }else{
            cout<<getsum(1,1,n,l,r)<<"\n";
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75