Submission #498600

#	Time	Username	Problem	Language	Result	Execution time	Memory
498600		beepbeepsheep	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	601 ms	21316 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define endl '\n'
typedef pair<ll,ll> ii;
const ll inf=1e15;
const ll maxn=5e5+5;
const ll mod=1e9+7;

struct node{
    ll s,e,m,val;
    node *l,*r;
    node(ll _s,ll _e):s(_s),e(_e),m((_s+_e)>>1),val(0){
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll p, ll v){
        if (s==e){val=v; return;}
        if (p>m) r->upd(p,v);
        if (p<=m) l->upd(p,v);
        val=l->val+r->val;
    }
    ll query(ll x, ll y){
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return l->query(x,y)+r->query(x,y);
    }
}*root;
set<ll> s;
ll arr[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,q,ele,k;
    cin>>n>>q>>k;
    root=new node(1,n);
    for (int i=1;i<=n;i++){
        cin>>ele;
        arr[i]=ele;
        root->upd(i,ele);
        if (arr[i]) s.insert(i);
    }
    ll t,a,b;
    for (int i=0;i<q;i++){
        cin>>t;
        t--;
        if (t==1){
            cin>>a>>b;
            if (k==1) continue;
            for (auto it=s.lower_bound(a);it!=s.end() && *it<=b;){
                root->upd(*it,arr[*it]/k);
                arr[*it]/=k;
                if (arr[*it]==0) it=s.erase(it);
                else it++;
            }
        }
        if (t==0){
            cin>>a>>b;
            arr[a]=b;
            root->upd(a,arr[a]);
            if (arr[a]) s.insert(a);
        }
        if (t==2){
            cin>>a>>b;
            cout<<root->query(a,b)<<endl;
        }
    }
    return 0;
}

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