oj.uz

Submission #1006201

# Submission time Handle Problem Language Result Execution time Memory
1006201 2024-06-23T14:25:03 Z 0pt1mus23 Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 5000 ms 3972 KB 
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 4*100000, inf = 2e18, prime = 23;
int T[sze];
void upd(int node,int idx,int l,int r,int v){
    if(l==r){
        T[node]=v;
        return;
    }
    int mid = (l+r)/2;
    if(idx<=mid){
        upd(2*node,idx,l,mid,v);
    }
    else{
        upd(2*node +1,idx,mid+1,r,v);
    }
    T[node]= T[2*node] + T[2*node +1];

}

void sil(int node,int l,int r,int lx,int rx,int v){
    // cout<<T[node]<<endl;
    if(lx>r || rx<l || T[node]==0){
        return;
    }
    if(lx==rx){
        // cout<<T[node]<<" silirem"<<endl;
        T[node]/=v;
        return;
    }
    int mid = lx+rx>>1;
    sil(2*node,l,r,lx,mid,v);
    sil(2*node +1,l,r,mid+1,rx,v);
    T[node]= T[2*node] + T[2*node +1];
}
int qry(int node,int l,int r,int lx,int rx){
    if(l>rx || lx>r){
        return 0;
    }
    if(lx>=l && rx<=r){
        return T[node];
    }
    int mid = lx+rx>>1;
    int left = qry(2*node,l,r,lx,mid);
    int right = qry(2*node +1,l,r,mid+1,rx);
    return left+right;
}

void mal(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        upd(1,i,0,n-1,x);
    }
    while(m--){
        int op;cin>>op;
        if(op==1){
            int idx,v;cin>>idx>>v;
            upd(1,--idx,0,n-1,v);
        }
        else if(op==2){
            int l,r;cin>>l>>r;
            --l;--r;
            sil(1,l,r,0,n-1,k);
            // cout<<"sildim: "<<T[1]<<endl;
        }
        else if(op==3){
            int l,r;cin>>l>>r;
            --l;--r;
            cout<<qry(1,l,r,0,n-1)<<endl;
        }

    }

}  


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        mal();        
    }
}

Compilation message

sterilizing.cpp: In function 'void sil(long long int, long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = lx+rx>>1;
      |               ~~^~~
sterilizing.cpp: In function 'long long int qry(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = lx+rx>>1;
      |               ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 3016 KB Output is correct
2 Correct 1047 ms 2932 KB Output is correct
3 Correct 1715 ms 2712 KB Output is correct
4 Correct 2633 ms 2984 KB Output is correct
5 Correct 3433 ms 2956 KB Output is correct
6 Correct 3369 ms 2924 KB Output is correct
7 Correct 3351 ms 2900 KB Output is correct
8 Correct 3425 ms 2900 KB Output is correct
9 Execution timed out 5054 ms 2652 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 604 KB Output is correct
2 Correct 8 ms 2652 KB Output is correct
3 Correct 11 ms 2668 KB Output is correct
4 Correct 28 ms 2648 KB Output is correct
5 Correct 43 ms 2648 KB Output is correct
6 Correct 38 ms 2652 KB Output is correct
7 Correct 4886 ms 2900 KB Output is correct
8 Correct 38 ms 3924 KB Output is correct
9 Correct 46 ms 3836 KB Output is correct
10 Correct 35 ms 3924 KB Output is correct
11 Correct 34 ms 3972 KB Output is correct
12 Correct 37 ms 3924 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2812 KB Output is correct
2 Correct 48 ms 2772 KB Output is correct
3 Correct 44 ms 2764 KB Output is correct
4 Correct 55 ms 2900 KB Output is correct
5 Correct 64 ms 2900 KB Output is correct
6 Correct 70 ms 2896 KB Output is correct
7 Correct 62 ms 2796 KB Output is correct
8 Correct 84 ms 2900 KB Output is correct
9 Correct 83 ms 2896 KB Output is correct
10 Correct 77 ms 2904 KB Output is correct
11 Correct 63 ms 2844 KB Output is correct
12 Correct 110 ms 2896 KB Output is correct