Submission #310080

#	Time	Username	Problem	Language	Result	Execution time	Memory
310080		mohamedsobhi777	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	298 ms	8216 KiB

sterilizing

#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 2e5 + 7 , mod = 1e9 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n, m , k ; 
ll tree[N * 4] ;  

void update(int node, int L , int R , int ix , int v){
        if(L == R){
                tree[node] = v ; 
                return ; 
        }
        int mid = (L + R) >> 1;
        if(ix <= mid)
                update(node*2+1 , L , mid , ix ,v) ; 
        else 
                update(node*2+2, mid + 1 , R , ix , v) ; 
        tree[node] = tree[node*2+1] + tree[node*2+2] ; 
}

void spray(int node , int L, int R , int l , int r){    
        if(l > R || r < L)
                return ;
        if(L == R){
                tree[node]/=k ; 
                return ; 
        } 
        if(L >= l && R <= r && tree[node] == 0){
                return ; 
        }
        int mid = (L + R) >> 1; 
        spray(node * 2 + 1, L , mid, l , r) ; 
        spray(node * 2 + 2, mid + 1 , R , l , r) ; 
        tree[node] = tree[node*2+1] + tree[node*2+2] ; 
}

ll query(int node, int L , int R , int l , int r){
        if(l > r || l > R || r < L)
                return 0 ; 
        if(L>= l && R <= r)
                return tree[node] ; 
        int mid = (L + R) >> 1 ; 
        ll s1 = query(node*2+1, L , mid , l , r) ; 
        ll s2 = query(node*2+2 , mid+1 , R , l , r) ; 
        return s1 + s2 ; 
}

int d1[N], d2[N], d3[N] ; 

ll bit[N], a[N]; 

inline void add(int ix, ll val){for(;ix<N;ix+=ix&-ix)bit[ix]+=val ; }
ll upto(int ix){
        ll ret = 0 ; 
        for(;ix;ix-=ix&-ix)ret+=bit[ix] ;
        return ret; 
}
inline ll get(int l, int r){return upto(r) - upto(l - 1) ; }

void solve1(){
        for(int i = 0 ;i < m; ++ i){
                if(d1[i] == 1){
                        add(d2[i] , d3[i] - a[d2[i]]) ; 
                        a[d2[i]] = d3[i] ; 
                }else if(d1[i] == 3){
                        cout<< get(d2[i] , d3[i]) <<"\n" ; 
                }
        }
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ;
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n >> m >> k ; 

        for(int i= 1; i <= n; ++ i){
                int x ; cin >> x ; 
                add(i , x) ; 
                a[i] = x; 
                update(0 , 1, N , i , x) ; 
        }
        for(int i = 0 ; i< m ; ++ i){
                cin >> d1[i] >> d2[i] >> d3[i] ; 
        }
        
        if(k == 1){
                solve1() ; 
                return 0; 
        }

        for(int i = 0 ;i < m ; ++ i){
                int t = d1[i], l = d2[i] , r = d3[i] ; 
                if(t == 1){
                        update(0 , 1, N, l , r) ; 
                }else if(t == 2){
                        if(k > 1) ; 
                                spray(0 , 1 , N , l , r) ; 
                }else{
                        cout<< query(0 ,1 , N, l , r) <<"\n" ;
                }
        }

        return 0 ; 
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:118:25: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  118 |                         if(k > 1) ;
      |                         ^~
sterilizing.cpp:119:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  119 |                                 spray(0 , 1 , N , l , r) ;
      |                                 ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75