oj.uz

Submission #661163

# Submission time Handle Problem Language Result Execution time Memory
661163 2022-11-24T19:22:42 Z Ahmed57 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1456 ms 12084 KB 
#include<bits/stdc++.h>
using namespace std;
long long arr[100001];
long long 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,long long 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];
}long long 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,long long>> 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--){
        long long ty,l,r;
        cin>>ty>>l>>r;
        if(ty==1){
            add(1,1,n,l,r);
            if(k!=1){
                pair<int,long long>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,long long> w = {l,0};
                auto it = s.lower_bound(w);
                while(it!=s.end()){
                    if((*it).first>r)break;
                    long long ww = (*it).second/k;
                    add(1,1,n,(*it).first,ww);
                    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 'long long 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 212 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 18 ms 496 KB Output is correct
5 Correct 19 ms 596 KB Output is correct
6 Correct 15 ms 660 KB Output is correct
7 Correct 19 ms 660 KB Output is correct
8 Correct 17 ms 660 KB Output is correct
9 Correct 22 ms 596 KB Output is correct
10 Correct 16 ms 596 KB Output is correct
11 Correct 17 ms 580 KB Output is correct
12 Correct 18 ms 636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 2044 KB Output is correct
2 Correct 119 ms 3520 KB Output is correct
3 Correct 110 ms 4916 KB Output is correct
4 Correct 130 ms 5612 KB Output is correct
5 Correct 156 ms 5972 KB Output is correct
6 Correct 161 ms 6052 KB Output is correct
7 Correct 171 ms 6056 KB Output is correct
8 Correct 157 ms 5968 KB Output is correct
9 Correct 164 ms 5808 KB Output is correct
10 Correct 159 ms 5880 KB Output is correct
11 Correct 151 ms 5892 KB Output is correct
12 Correct 150 ms 5888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 700 KB Output is correct
2 Correct 35 ms 3048 KB Output is correct
3 Correct 47 ms 3096 KB Output is correct
4 Correct 127 ms 1868 KB Output is correct
5 Correct 159 ms 6248 KB Output is correct
6 Correct 162 ms 6324 KB Output is correct
7 Correct 133 ms 3272 KB Output is correct
8 Correct 162 ms 6488 KB Output is correct
9 Correct 145 ms 6212 KB Output is correct
10 Correct 145 ms 6252 KB Output is correct
11 Correct 151 ms 6244 KB Output is correct
12 Correct 151 ms 6204 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 5080 KB Output is correct
2 Correct 347 ms 6832 KB Output is correct
3 Correct 625 ms 5764 KB Output is correct
4 Correct 419 ms 4952 KB Output is correct
5 Correct 598 ms 12084 KB Output is correct
6 Correct 763 ms 12008 KB Output is correct
7 Correct 564 ms 12024 KB Output is correct
8 Correct 996 ms 12056 KB Output is correct
9 Correct 805 ms 12060 KB Output is correct
10 Correct 984 ms 12064 KB Output is correct
11 Correct 627 ms 11912 KB Output is correct
12 Correct 1456 ms 11936 KB Output is correct