Submission #1289946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289946		metric	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5091 ms	5728 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
struct node{long long s,m;} t[400005];
int n,q,k;vector<long long> a;
void bld(int id,int l,int r){
    if(l==r){t[id]={a[l],a[l]};return;}
    int m=(l+r)/2;
    bld(id*2,l,m);bld(id*2+1,m+1,r);
    t[id].s=t[id*2].s+t[id*2+1].s;
    t[id].m=max(t[id*2].m,t[id*2+1].m);
}
void upd1(int id,int l,int r,int p,long long v){
    if(l==r){t[id]={v,v};return;}
    int m=(l+r)/2;
    if(p<=m)upd1(id*2,l,m,p,v);
    else upd1(id*2+1,m+1,r,p,v);
    t[id].s=t[id*2].s+t[id*2+1].s;
    t[id].m=max(t[id*2].m,t[id*2+1].m);
}
void spray(int id,int l,int r,int u,int v){
    if(t[id].m==0||r<u||v<l) return;
    if(l==r){t[id].s/=k;t[id].m=t[id].s;return;}
    int m=(l+r)/2;
    spray(id*2,l,m,u,v);spray(id*2+1,m+1,r,u,v);
    t[id].s=t[id*2].s+t[id*2+1].s;
    t[id].m=max(t[id*2].m,t[id*2+1].m);
}
long long get(int id,int l,int r,int u,int v){
    if(r<u||v<l) return 0;
    if(u<=l&&r<=v) return t[id].s;
    int m=(l+r)/2;
    return get(id*2,l,m,u,v)+get(id*2+1,m+1,r,u,v);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>k;a.resize(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    bld(1,1,n);
    while(q--){
        int s,t,u;cin>>s>>t>>u;
        if(s==1) upd1(1,1,n,t,u);
        else if(s==2) spray(1,1,n,t,u);
        else cout<<get(1,1,n,t,u)<<"\n";
    }
}

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