oj.uz

Submission #1006312

# Submission time Handle Problem Language Result Execution time Memory
1006312 2024-06-23T18:22:06 Z 0pt1mus23 Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 5000 ms 3668 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 344 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 1476 ms 2976 KB Output is correct
2 Correct 955 ms 2896 KB Output is correct
3 Correct 1492 ms 2928 KB Output is correct
4 Correct 2374 ms 2828 KB Output is correct
5 Correct 3146 ms 3040 KB Output is correct
6 Correct 3119 ms 3060 KB Output is correct
7 Correct 3097 ms 3200 KB Output is correct
8 Correct 3295 ms 2992 KB Output is correct
9 Execution timed out 5051 ms 2676 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 2652 KB Output is correct
3 Correct 8 ms 2648 KB Output is correct
4 Correct 24 ms 2688 KB Output is correct
5 Correct 26 ms 2708 KB Output is correct
6 Correct 24 ms 2648 KB Output is correct
7 Correct 4781 ms 2796 KB Output is correct
8 Correct 31 ms 3668 KB Output is correct
9 Correct 26 ms 3416 KB Output is correct
10 Correct 26 ms 3420 KB Output is correct
11 Correct 32 ms 3496 KB Output is correct
12 Correct 26 ms 3420 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2648 KB Output is correct
2 Correct 62 ms 2728 KB Output is correct
3 Correct 41 ms 2648 KB Output is correct
4 Correct 55 ms 2900 KB Output is correct
5 Correct 53 ms 2768 KB Output is correct
6 Correct 57 ms 2900 KB Output is correct
7 Correct 49 ms 2792 KB Output is correct
8 Correct 66 ms 2900 KB Output is correct
9 Correct 62 ms 2900 KB Output is correct
10 Correct 64 ms 2896 KB Output is correct
11 Correct 50 ms 2904 KB Output is correct
12 Correct 82 ms 2796 KB Output is correct