Submission #484479

#	Time	Username	Problem	Language	Result	Execution time	Memory
484479		Mahdi	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	1688 ms	7352 KiB

sterilizing

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define F first
#define S second
typedef long long ll;
const int N=1e5+5;
int n, q, k, sz, c[N], mx[3*N];
ll sg[3*N];

void st(int x){
    x+=sz-1;
    sg[x]=c[x-sz+1];
    while(x){
        --x;
        x/=2;
        mx[x]=(c[mx[2*x+1]]<c[mx[2*x+2]]? mx[2*x+2] : mx[2*x+1]);
        sg[x]=sg[2*x+1]+sg[2*x+2];
    }
}

ll sum(int x, int lx, int rx, int l, int r){
    if(lx>=r || rx<=l)
        return 0;
    if(lx>=l && rx<=r)
        return sg[x];
    int m=(lx+rx)/2;
    return sum(2*x+1, lx, m, l, r)+sum(2*x+2, m, rx, l, r);
}

int seg(int x, int lx, int rx, int l, int r){
    if(lx>=r || rx<=l)
        return n;
    if(lx>=l && rx<=r)
        return mx[x];
    int m=(lx+rx)/2;
    int L=seg(2*x+1, lx, m, l, r), R=seg(2*x+2, m, rx, l, r);
    return (c[L]<c[R] ? R : L);
}

void opr(int l, int r){
    if(k==1)
        return;
    vector<pii>v;
    int z=seg(0, 0, sz, l, r);
    while(c[z]){
        v.push_back({z, c[z]/k});
        c[z]=0;
        st(z);
        z=seg(0, 0, sz, l, r);
    }
    for(auto u:v){
        c[u.F]=u.S;
        st(u.F);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q>>k;
    for(int i=0;i<n;++i)
        cin>>c[i];
    sz=1;
    while(sz<n)
        sz<<=1;
    iota(mx+sz-1, mx+sz+n-1, 0);
    for(int i=sz-1;i<sz+n-1;++i)
        sg[i]=c[i-sz+1];
    for(int i=sz-2;i>=0;--i){
        sg[i]=sg[2*i+1]+sg[2*i+2];
        mx[i]=(c[mx[2*i+1]]<c[mx[2*i+2]] ? mx[2*i+2] : mx[2*i+1]);
    }
    int s, t, u;
    while(q--){
        cin>>s>>t>>u;
        if(s==1){
            c[--t]=u;
            st(t);
        }
        else if(s==2)
            opr(--t, u);
        else
            cout<<sum(0, 0, sz, --t, u)<<'\n';
    }
}

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