oj.uz

Submission #310080

# Submission time Handle Problem Language Result Execution time Memory
310080 2020-10-05T15:42:15 Z mohamedsobhi777 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 298 ms 8216 KB 
#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

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.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3960 KB Output is correct
2 Correct 38 ms 4728 KB Output is correct
3 Correct 41 ms 5880 KB Output is correct
4 Correct 51 ms 7416 KB Output is correct
5 Correct 58 ms 8184 KB Output is correct
6 Correct 58 ms 8184 KB Output is correct
7 Correct 67 ms 8184 KB Output is correct
8 Correct 63 ms 8216 KB Output is correct
9 Correct 59 ms 8056 KB Output is correct
10 Correct 59 ms 8184 KB Output is correct
11 Correct 59 ms 8056 KB Output is correct
12 Correct 59 ms 8056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1152 KB Output is correct
2 Correct 20 ms 2176 KB Output is correct
3 Correct 26 ms 2304 KB Output is correct
4 Correct 64 ms 2552 KB Output is correct
5 Correct 89 ms 5368 KB Output is correct
6 Correct 90 ms 5240 KB Output is correct
7 Correct 50 ms 5880 KB Output is correct
8 Correct 89 ms 6776 KB Output is correct
9 Correct 83 ms 6608 KB Output is correct
10 Correct 85 ms 6520 KB Output is correct
11 Correct 86 ms 6648 KB Output is correct
12 Correct 82 ms 6520 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3232 KB Output is correct
2 Correct 111 ms 3448 KB Output is correct
3 Correct 126 ms 2808 KB Output is correct
4 Correct 137 ms 2936 KB Output is correct
5 Correct 162 ms 5496 KB Output is correct
6 Correct 187 ms 5496 KB Output is correct
7 Correct 157 ms 5500 KB Output is correct
8 Correct 222 ms 5576 KB Output is correct
9 Correct 205 ms 5752 KB Output is correct
10 Correct 230 ms 5624 KB Output is correct
11 Correct 174 ms 5496 KB Output is correct
12 Correct 298 ms 5524 KB Output is correct