Submission #1128368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128368		ngokhanh	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	172 ms	4988 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define rep2(i,a,b,c) for (int i=a;i<=b;i+=c)
#define rev(i,a,b) for (int i=a;i>=b;i--)
#define rev2(i,a,b,c) for (int i=a;i>=b;i-=c)
#define bit(i,j) ((i>>j)&1)
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define ll long long
#define Fi first
#define Se second
#define on(n) __builtin_popcountll(n)
#define ld long double
#define __log2(x) 31-__builtin_clz(x)
#define Mask(x) (1LL<<x)
#define ALL(v) v.begin(),v.end()

const int MAXN=1e5+5;
const int mod=998244353;

int n,q,K,x,l,r,type;

struct IT{

    ll stSum[4*MAXN],stMax[4*MAXN];

    void updateRange(int x,int l,int r,int u,int v){
        if (v<l||r<u||l>r||stMax[x]==0) return;
        if (l==r){
            stSum[x]/=K;
            stMax[x]=stSum[x];
            return;
        }
        int mid=(l+r)/2;
        updateRange(x*2,l,mid,u,v);
        updateRange(x*2+1,mid+1,r,u,v);
        stSum[x]=stSum[x*2]+stSum[x*2+1];
        stMax[x]=max(stMax[x*2],stMax[x*2+1]);
    }

    void updatePos(int x,int l,int r,int pos,int val){
        if (pos<l||r<pos||l>r) return;
        if (l==r){
            stSum[x]=stMax[x]=val;
            return;
        }
        int mid=(l+r)/2;
        updatePos(x*2,l,mid,pos,val);
        updatePos(x*2+1,mid+1,r,pos,val);
        stSum[x]=stSum[x*2]+stSum[x*2+1];
        stMax[x]=max(stMax[x*2],stMax[x*2+1]);
    }

    ll get(int x,int l,int r,int u,int v){
        if (v<l||r<u||l>r) return 0;
        if (u<=l&&r<=v) return stSum[x];
        int mid=(l+r)/2;
        return get(x*2,l,mid,u,v)+get(x*2+1,mid+1,r,u,v);
    }

    void UpdRange(int l,int r) {updateRange(1,1,n,l,r);};
    void UpdPos(int pos,int val) {updatePos(1,1,n,pos,val);};

    ll Get(int l,int r) {return get(1,1,n,l,r); };

};

IT tree;

void solution(){
    cin >> n >> q >> K;
    rep(i,1,n){
        cin >> x;
        tree.UpdPos(i,x);
    }
    while(q--){
        cin >> type >> l >> r;
        if (type==1) tree.UpdPos(l,r);
        if (type==2&&K!=1) tree.UpdRange(l,r);
        if (type==3) cout << tree.Get(l,r) << '\n';
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test=1;
    while(test--)
        solution();
}

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