oj.uz

Submission #894628

# Submission time Handle Problem Language Result Execution time Memory
894628 2023-12-28T14:36:07 Z IWKR Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 292 ms 16048 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct node{
    int s,m,e,v=0;
    node *l, *r;
    node(int S, int E){
        e=E,s=S,m=(s+e)>>1;
        if (s!=e) {
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void add(int S, int E, int V){
        if(v==0){return;}
        if(s==e){v/=V;return;}
        if(E<=m)l->add(S,E,V);
        else if(S>m)r->add(S,E,V);
        else{
            l->add(S,m,V);
            r-> add(m+1,E,V);
        } 
        v=l->v+r->v;
    }
    void update(int X, int V) {
        if(s==e){
            v=V;
        }else{
            if(X<=m){
                l->update(X,V);
            }else{
                r->update(X,V);
            }
            v=l->v+r->v;
        }
    }
    int sum(int S, int E){
        if(s==S&&e==E)return v;
        if(E<=m)return l->sum(S,E);
        else if(S>m)return r->sum(S,E);
        else return (l->sum(S,m)) + (r->sum(m+1,E));
    }
} *root;
int t,a,b,n,q,k;
signed main(){
    cin>>n>>q>>k;
    root=new node(0,n-1);
    for(int i=0;i<n;i++) {
        cin>>a;
        root->update(i,a);
    }
    while(q--){
        cin>>t>>a>>b;
        a--;
        b--;
        if(t==2){
			if(k==1)continue;
            root->add(a,b,k);
        }else if(t==3){
            cout<<root->sum(a,b)<<'\n';
        }else{
            b++;
            root->update(a,b);
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 6 ms 880 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 7 ms 860 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 7 ms 856 KB Output is correct
10 Correct 6 ms 860 KB Output is correct
11 Correct 6 ms 860 KB Output is correct
12 Correct 6 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 8832 KB Output is correct
2 Correct 124 ms 6420 KB Output is correct
3 Correct 132 ms 12112 KB Output is correct
4 Correct 173 ms 15176 KB Output is correct
5 Correct 176 ms 15688 KB Output is correct
6 Correct 195 ms 16048 KB Output is correct
7 Correct 176 ms 15732 KB Output is correct
8 Correct 164 ms 15860 KB Output is correct
9 Correct 177 ms 15696 KB Output is correct
10 Correct 171 ms 15696 KB Output is correct
11 Correct 166 ms 15612 KB Output is correct
12 Correct 167 ms 15904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1612 KB Output is correct
2 Correct 30 ms 6312 KB Output is correct
3 Correct 40 ms 6436 KB Output is correct
4 Correct 138 ms 4648 KB Output is correct
5 Correct 158 ms 14384 KB Output is correct
6 Correct 153 ms 14348 KB Output is correct
7 Correct 150 ms 14544 KB Output is correct
8 Correct 150 ms 14364 KB Output is correct
9 Correct 138 ms 14092 KB Output is correct
10 Correct 134 ms 14212 KB Output is correct
11 Correct 143 ms 14416 KB Output is correct
12 Correct 135 ms 14296 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 8532 KB Output is correct
2 Correct 151 ms 8788 KB Output is correct
3 Correct 134 ms 7248 KB Output is correct
4 Correct 174 ms 6272 KB Output is correct
5 Correct 216 ms 15504 KB Output is correct
6 Correct 230 ms 15456 KB Output is correct
7 Correct 239 ms 15504 KB Output is correct
8 Correct 258 ms 15672 KB Output is correct
9 Correct 226 ms 15440 KB Output is correct
10 Correct 230 ms 15364 KB Output is correct
11 Correct 198 ms 15500 KB Output is correct
12 Correct 292 ms 15352 KB Output is correct