Submission #398686

#	Time	Username	Problem	Language	Result	Execution time	Memory
398686		Yeboi	Sterilizing Spray (JOI15_sterilizing)	C++14	10 / 100	213 ms	8212 KiB

sterilizing

#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
const ll INF = 1000000000;
const ll N = 500005;
const ll MOD = 1000000007;
const ll MAXN = 10000000000;
const ll rootval = 319;
using namespace std;

// segtree with poll updates , spraying function, sum query
// as used in that codeforces SUM AND REPLACE prob idea is after log10 number of divisions element will become 0 so we will check if max of curr seg is >0
// then only apply operation
ll treesum[4*N], treemax[4*N];
ll arr[N];
ll n,k;
void build(ll v, ll tl, ll tr) {
    if (tl == tr) {
        treesum[v] = arr[tl];
        treemax[v] = arr[tl];
    } else {
        ll tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        treesum[v] = treesum[v*2] + treesum[v*2+1];
        treemax[v] = treemax[v*2] + treemax[v*2+1];
    }
}
ll sum1(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return treesum[v];
    }
    ll tm = (tl + tr) / 2;
    return sum1(v*2, tl, tm, l, min(r, tm))
           + sum1(v*2+1, tm+1, tr, max(l, tm+1), r);
}
ll sum(ll l, ll r){
    return sum1(1,1,n,l,r);
}   
void update1(ll v, ll tl, ll tr, ll pos, ll new_val) {
    if (tl == tr) {
        treesum[v] = new_val;
        treemax[v] = new_val;
    } else {
        ll tm = (tl + tr) / 2;
        if (pos <= tm)
            update1(v*2, tl, tm, pos, new_val);
        else
            update1(v*2+1, tm+1, tr, pos, new_val);
        treesum[v] = treesum[v*2] + treesum[v*2+1];
        treemax[v] = max(treemax[v],treemax[v*2+1]);
    }
}
void update(ll pos , ll new_val){
    update1(1,1,n,pos,new_val);
    return;
}
void spray_fun(ll v, ll tl, ll tr, ll l, ll r){
    if(tr < l || tl > r){
        return;
    }
    if(tl == tr){
        treesum[v] = treesum[v]/k;
        treemax[v] = treemax[v]/k;
        return;
    }
    if(treemax[v] == 0 || k == 1){
        return;
    }
    ll tm = (tl+tr)/2;
    spray_fun(2*v,tl,tm,l,min(r,tm));
    spray_fun(2*v+1,tm+1,tr,max(l,tm+1),r);
    treesum[v] = treesum[2*v] + treesum[2*v+1];
    treemax[v] = treemax[2*v] + treemax[2*v+1];
}
void spray(ll l , ll r){
    spray_fun(1,1,n,l,r);
}
int main(){
    ll q;
    cin >> n >> q >> k;
    f(i,1,n+1){
        ll val;
        cin >> val;
        arr[i] = val;
    }
    build(1,1,n);
    rep(i,q){
        ll s,l,r;
        cin >> s >> l >> r;
        if(s == 1){
            update(l,r);
        }
        else if(s == 2){
            spray(l,r);
        }
        else if(s == 3){
            cout << sum(l,r) << endl;
        }
    }
} 

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