Submission #1136271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136271		onlk97	Sterilizing Spray (JOI15_sterilizing)	C++20	10 / 100	63 ms	7868 KiB

sterilizing

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
using tii=pair <pii,int>;
int n,k;
int a[400040],mn[400040],mx[400040],sum[400040],laz[400040],pw[400040];
void pushup(int id){
    mn[id]=min(mn[2*id],mn[2*id+1]);
    mx[id]=max(mx[2*id],mx[2*id+1]);
    sum[id]=sum[2*id]+sum[2*id+1];
}
void pushdown(int id,int tl,int tr){
    if (!laz[id]) return;
    int tm=(tl+tr)/2;
    mn[2*id]/=pw[laz[id]]; mn[2*id+1]/=pw[laz[id]];
    mx[2*id]/=pw[laz[id]]; mx[2*id+1]/=pw[laz[id]];
    sum[2*id]=(tm-tl+1)*mn[2*id]; sum[2*id+1]=(tr-tm)*mn[2*id+1];
    laz[2*id]+=laz[id]; laz[2*id+1]+=laz[id];
    laz[id]=0;
}
void build(int id,int tl,int tr){
    if (tl==tr){
        mn[id]=a[tl]; mx[id]=a[tl]; sum[id]=a[tl];
        return;
    }
    int tm=(tl+tr)/2;
    build(2*id,tl,tm);
    build(2*id+1,tm+1,tr);
    pushup(id);
}
void update1(int id,int tl,int tr,int pos,int val){
    if (tl==tr){
        mn[id]=val; mx[id]=val; sum[id]=val;
        return;
    }
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    if (pos<=tm) update1(2*id,tl,tm,pos,val);
    else update1(2*id+1,tm+1,tr,pos,val);
    pushup(id);
}
void update2(int id,int tl,int tr,int l,int r){
    if (l>r) return;
    if (l<=tl&&tr<=r&&mn[id]/k==mx[id]/k){
        mn[id]/=k;
        mx[id]/=k;
        sum[id]=(tr-tl+1)*mn[id];
        laz[id]++;
        return;
    }
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    update2(2*id,tl,tm,l,min(r,tm));
    update2(2*id+1,tm+1,tr,max(l,tm+1),r);
    pushup(id);
}
int query(int id,int tl,int tr,int l,int r){
    if (l>r) return 0;
    if (l<=tl&&tr<=r) return sum[id];
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    int lx=query(2*id,tl,tm,l,min(r,tm));
    int rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
    return lx+rx;
}
void solve(){
    int q;
    cin>>n>>q>>k;
    if (k>=2){
        pw[0]=1;
        for (int i=1; i<=q; i++){
            if (pw[i-1]>2e15/k) pw[i]=0;
            else pw[i]=pw[i-1]*k;
        }
    }
    for (int i=1; i<=n; i++) cin>>a[i];
    build(1,1,n);
    while (q--){
        int type,l,r; cin>>type>>l>>r;
        if (type==1) update1(1,1,n,l,r);
        else if (type==2&&k>1) update2(1,1,n,l,r);
        else if (type==3){
            int tp=query(1,1,n,l,r);
            cout<<tp<<'\n';
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

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