Submission #1207463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207463		minhpk	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	132 ms	5708 KiB

sterilizing

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int f[4000005];
int f1[4000005];
int z[1000005];
void build(int id,int l,int r){
    if (l==r){
        f[id]=z[l];
        f1[id]=z[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    f[id]=f[id*2]+f[id*2+1];
    f1[id]=max(f1[id*2+1],f1[id*2]);
}

void update1(int id,int l,int r,int pos,int val){
    if (l==r){
        f[id]=val;
        f1[id]=val;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid){
        update1(id*2,l,mid,pos,val);
    }else{
        update1(id*2+1,mid+1,r,pos,val);
    }
    f[id]=f[id*2]+f[id*2+1];
    f1[id]=max(f1[id*2+1],f1[id*2]);
}

void update(int id,int l,int r,int x,int y){
    if (x>r || y<l || f1[id]==0){
        return;
    }
    if (l==r){
        f[id]/=c;
        f1[id]/=c;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,x,y);
    update(id*2+1,mid+1,r,x,y);
    f[id]=f[id*2]+f[id*2+1];
    f1[id]=max(f1[id*2+1],f1[id*2]);
}

int get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return 0;
    }
    if (l>=x && y>=r){
        return f[id];
    }
    int mid=(l+r)/2;
    return get(id*2,l,mid,x,y)+get(id*2+1,mid+1,r,x,y);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> c;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }
    build(1,1,a);
    for (int i=1;i<=b;i++){
         int t,x,y;
         cin >>  t >> x >> y;
         if (t==1){
             update1(1,1,a,x,y);
         }else if (t==2){
             if (c==1){
                continue;
             }
             update(1,1,a,x,y);
         }else{
             cout << get(1,1,a,x,y) << "\n";
         }
    }
    return 0;
}

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