oj.uz

Submission #1006204

# Submission time Handle Problem Language Result Execution time Memory
1006204 2024-06-23T14:29:53 Z 0pt1mus23 Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 5000 ms 3156 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>>1;
    if(idx<=mid){
        upd((node<<1),idx,l,mid,v);
    }
    else{
        upd((node<<1) +1,idx,mid+1,r,v);
    }
    T[node]= T[(node<<1)] + T[(node<<1) +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((node<<1),l,r,lx,mid,v);
    sil((node<<1) +1,l,r,mid+1,rx,v);
    T[node]= T[(node<<1)] + T[(node<<1) +1];
}
int qry(int node,int l,int r,int lx,int rx){
    if(l>rx || lx>r || T[node]==0){
        return 0;
    }
    if(lx>=l && rx<=r){
        return T[node];
    }
    int mid = lx+rx>>1;
    int left = qry((node<<1),l,r,lx,mid);
    int right = qry((node<<1) +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;
        if(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 upd(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l+r>>1;
      |               ~^~
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 348 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 1588 ms 2936 KB Output is correct
2 Correct 962 ms 2896 KB Output is correct
3 Correct 1527 ms 2932 KB Output is correct
4 Correct 2512 ms 2980 KB Output is correct
5 Correct 3143 ms 2896 KB Output is correct
6 Correct 3261 ms 3156 KB Output is correct
7 Correct 3170 ms 2952 KB Output is correct
8 Correct 3204 ms 2900 KB Output is correct
9 Execution timed out 5048 ms 2732 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 6 ms 2692 KB Output is correct
3 Correct 8 ms 2604 KB Output is correct
4 Correct 19 ms 2720 KB Output is correct
5 Correct 24 ms 2720 KB Output is correct
6 Correct 28 ms 2652 KB Output is correct
7 Correct 4925 ms 2648 KB Output is correct
8 Correct 29 ms 2648 KB Output is correct
9 Correct 27 ms 2652 KB Output is correct
10 Correct 28 ms 2652 KB Output is correct
11 Correct 33 ms 2648 KB Output is correct
12 Correct 26 ms 2648 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2652 KB Output is correct
2 Correct 43 ms 2692 KB Output is correct
3 Correct 45 ms 2652 KB Output is correct
4 Correct 53 ms 2896 KB Output is correct
5 Correct 60 ms 2896 KB Output is correct
6 Correct 59 ms 2900 KB Output is correct
7 Correct 56 ms 2900 KB Output is correct
8 Correct 77 ms 2792 KB Output is correct
9 Correct 69 ms 2896 KB Output is correct
10 Correct 70 ms 2900 KB Output is correct
11 Correct 57 ms 2896 KB Output is correct
12 Correct 99 ms 2936 KB Output is correct