Submission #204487

#	Time	Username	Problem	Language	Result	Execution time	Memory
204487		aloo123	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	363 ms	8184 KiB

sterilizing

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
using namespace std;

const ll N = 1e5+5;
const ll MOD = 1e9+7;
ll tree[4LL*N];


ll a[N];
ll k;
ll ma[4LL*N];
ll LOG(ll n){
    ll ans = 0;
    while(n){
        ans += 1;
        n /= k;
    }
    return ans;
}
void merge(ll node){
    tree[node] = tree[node*2] + tree[node*2+1];
    ma[node] = max(ma[node*2],ma[node*2+1]);
}

void build(ll node,ll l,ll r){
    if(l==r){
        tree[node] = a[l];
        ma[node] = a[l];
    }
    else{
        ll mid = (l+r)/2;
        build(node * 2,l,mid);
        build(node * 2 + 1,mid+1,r);
        merge(node);
    }
}

void update(ll node,ll l,ll r,ll idx,ll val){
    if(l == r){
        tree[node] = val;
        ma[node] = val;
    }
    else{
        ll mid = (l+r)/2;
        if(idx <= mid) update(node * 2,l,mid,idx,val);
        else update(node * 2 +1,mid+1,r,idx,val);
        merge(node);
    }
}

void update2(ll node,ll l,ll r,ll st,ll en){
     if(l > en || r < st) return ;
     if(l >= st && r<=en){
        if(ma[node] == 0) return;
         if(l == r){
             
             tree[node] /= k;
             ma[node] /= k;
            return;
         }}
    ll mid = (l+r)/2;
    update2(node*2,l,mid,st,en);
    update2(node*2+1,mid+1,r,st,en);
    merge(node);
}

ll query(ll node,ll l,ll r,ll st,ll en){
    if(l > en || r < st) return 0;
    if(l >= st && r<=en) return tree[node];
    ll mid =(l+r)/2;
    ll p1 = query(node*2,l,mid,st,en);
    ll p2 = query(node*2+1,mid+1,r,st,en);
    return p1 +p2;
}

int main()
{


    ios_base::sync_with_stdio(0);
    cin.tie(0);


    ll n,q;
    cin >> n >> q >> k;


    for(int i = 1;i<=n;i++) cin >> a[i];
    build(1,1,n);
    while(q--){
        ll t,l,r;
        cin>> t>> l >> r;
        if(t == 1){
            update(1,1,n,l,r);
        }
        else if(t==2){
            if(k != 1)
            update2(1,1,n,l,r);
        }
        else{
            cout << query(1,1,n,l,r) << endl;
        }
    }


    return 0;
}

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