oj.uz

Submission #661161

# Submission time Handle Problem Language Result Execution time Memory
661161 2022-11-24T19:18:42 Z Ahmed57 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 338 ms 8020 KB 
#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(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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 3268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1280 KB Output is correct
2 Correct 41 ms 3284 KB Output is correct
3 Correct 55 ms 3384 KB Output is correct
4 Correct 132 ms 2960 KB Output is correct
5 Correct 183 ms 7888 KB Output is correct
6 Correct 188 ms 8020 KB Output is correct
7 Correct 141 ms 3316 KB Output is correct
8 Correct 174 ms 7828 KB Output is correct
9 Correct 165 ms 7708 KB Output is correct
10 Correct 199 ms 7632 KB Output is correct
11 Correct 170 ms 7668 KB Output is correct
12 Correct 171 ms 7660 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 338 ms 5080 KB Output isn't correct
2 Halted 0 ms 0 KB -