oj.uz

Submission #1006202

# Submission time Handle Problem Language Result Execution time Memory
1006202 2024-06-23T14:26:38 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(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 || T[node]==0){
        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 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 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 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 388 KB Output is correct
9 Correct 4 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 1806 ms 3084 KB Output is correct
2 Correct 1137 ms 2896 KB Output is correct
3 Correct 1695 ms 2896 KB Output is correct
4 Correct 2780 ms 2996 KB Output is correct
5 Correct 3486 ms 3132 KB Output is correct
6 Correct 3569 ms 2900 KB Output is correct
7 Correct 3451 ms 2896 KB Output is correct
8 Correct 3537 ms 3156 KB Output is correct
9 Execution timed out 5050 ms 2776 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 7 ms 2652 KB Output is correct
3 Correct 10 ms 2704 KB Output is correct
4 Correct 25 ms 2720 KB Output is correct
5 Correct 27 ms 2692 KB Output is correct
6 Correct 29 ms 2648 KB Output is correct
7 Correct 4699 ms 2896 KB Output is correct
8 Correct 31 ms 2652 KB Output is correct
9 Correct 30 ms 2660 KB Output is correct
10 Correct 44 ms 2732 KB Output is correct
11 Correct 28 ms 2652 KB Output is correct
12 Correct 28 ms 2648 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2652 KB Output is correct
2 Correct 38 ms 2800 KB Output is correct
3 Correct 42 ms 2652 KB Output is correct
4 Correct 51 ms 2920 KB Output is correct
5 Correct 67 ms 2900 KB Output is correct
6 Correct 65 ms 2828 KB Output is correct
7 Correct 58 ms 2896 KB Output is correct
8 Correct 75 ms 2972 KB Output is correct
9 Correct 81 ms 2900 KB Output is correct
10 Correct 72 ms 2896 KB Output is correct
11 Correct 58 ms 2904 KB Output is correct
12 Correct 118 ms 2896 KB Output is correct