oj.uz

Submission #661162

# Submission time Handle Problem Language Result Execution time Memory
661162 2022-11-24T19:20:10 Z Ahmed57 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 340 ms 4188 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(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

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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 1480 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 50 ms 556 KB Output is correct
2 Correct 35 ms 2028 KB Output is correct
3 Correct 46 ms 2004 KB Output is correct
4 Correct 131 ms 1236 KB Output is correct
5 Correct 159 ms 4116 KB Output is correct
6 Correct 163 ms 4072 KB Output is correct
7 Correct 129 ms 1868 KB Output is correct
8 Correct 159 ms 4100 KB Output is correct
9 Correct 155 ms 4088 KB Output is correct
10 Correct 160 ms 4188 KB Output is correct
11 Correct 156 ms 4048 KB Output is correct
12 Correct 148 ms 4104 KB Output is correct

Subtask #4
0 / 75.0

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