Submission #1238933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238933		lambd47	Sterilizing Spray (JOI15_sterilizing)	C++17	10 / 100	48 ms	6984 KiB

sterilizing

#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

struct node{
    int nz,val;
    node(){
        nz=0;val=0;
    }
    node(int x){
        nz=1;
        val=x;
    }
    node(int x, int y){
        nz=x;
        val=y;
    }
    node operator+(const node& aux)const {
        return node(nz+aux.nz,val+aux.val);
    }
};
const int MX=1e5+7;
node seg[4*MX];

int k;
void upd1(int pos, int ini, int fim, int id, int val){
    if(ini>id ||fim<id)return;
    if(ini==fim){
        seg[pos].nz=(int)(val!=0);
        seg[pos].val=val;
        return;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    upd1(e,ini,m,id,val);
    upd1(d,m+1,fim,id,val);
    seg[pos]=seg[e]+seg[d];
    return;
}
void upd2(int pos, int ini, int fim, int l, int r){
    if(seg[pos].nz == 0)return;
    if(ini>r || fim<l) return;
    if(ini==fim){
        seg[pos].val/=k;
        seg[pos].nz=(int)(seg[pos].val!=0);
        return;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    upd2(e,ini,m,l,r);
    upd2(d,m+1,fim,l,r);
    seg[pos]=seg[e]+seg[d];
    return;
}
int query(int pos, int ini, int fim,int l, int r){
    if(fim<l || ini>r)return 0;
    if(l<= ini && fim <= r){
        return seg[pos].val;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    return query(e,ini,m,l,r)+query(d,m+1,fim,l,r);
}

void solve() {
    int n,q;cin>>n>>q>>k;
    L(i,0,n-1){
        int x;cin>>x;
        upd1(1,0,n-1,i,x);
    }
    while(q--){
        int tipo;cin>>tipo;
        if(tipo==1){
            int a,b;cin>>a>>b;
            a--;
            upd1(1,0,n-1,a,b);
        }
        else if(tipo==2){
            int l,r;cin>>l>>r;
            continue;
            l--;r--;
            upd2(1,0,n-1,l,r);
        }
        else{
            int l,r;cin>>l>>r;
            l--;r--;
            cout<<query(1,0,n-1,l,r)<<"\n";
        }
    }



}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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