Submission #661162

#	Time	Username	Problem	Language	Result	Execution time	Memory
661162		Ahmed57	Sterilizing Spray (JOI15_sterilizing)	C++14	10 / 100	340 ms	4188 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
int arr[100001];
int seg[400001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = arr[l];
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = seg[p*2]+seg[p*2+1];
}
void add(int p,int l,int r,int idx,int val){
    if(l==r){
        seg[p] = val;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)add(p*2,l,md,idx,val);
    else add(p*2+1,md+1,r,idx,val);
    seg[p] = seg[p*2]+seg[p*2+1];
}int qu(int p,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq)return seg[p];if(r<lq||l>rq)return 0;
    int md = (l+r)/2;
    return qu(p*2,l,md,lq,rq)+qu(p*2+1,md+1,r,lq,rq);
}
int main(){
    int n,q,k;
    cin>>n>>q>>k;
    set<pair<int,int>> s;
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
        if(arr[i]==0)continue;
        if(k!=1)s.insert({i,arr[i]});
    }
    build(1,1,n);
    while(q--){
        int ty,l,r;
        cin>>ty>>l>>r;
        if(ty==1){
            add(1,1,n,l,r);
            if(k!=1){
                pair<int,int>w = {l,0};
                auto it = s.lower_bound(w);
                if(it!=s.end()&&(*it).first==l){
                    s.erase(it);
                }
                s.insert({l,r});
            }
        }else if(ty==2){
            if(k!=1){
                pair<int,int> w = {l,0};
                auto it = s.lower_bound(w);
                while(it!=s.end()){
                    if((*it).first>r)break;
                    add(1,1,n,(*it).first,(*it).second/k);
                    int ww = (*it).second/k;
                    w.first = (*it).first+1;
                    s.erase(it);
                    if(ww!=0)s.insert({w.first-1,ww});
                    it = s.lower_bound(w);
                }
            }
        }else{
            cout<<qu(1,1,n,l,r)<<"\n";
        }
    }
}

Compilation message (stderr)

sterilizing.cpp: In function 'int qu(int, int, int, int, int)':
sterilizing.cpp:25:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   25 |     if(l>=lq&&r<=rq)return seg[p];if(r<lq||l>rq)return 0;
      |     ^~
sterilizing.cpp:25:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |     if(l>=lq&&r<=rq)return seg[p];if(r<lq||l>rq)return 0;
      |                                   ^~

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