oj.uz

Submission #310079

# Submission time Handle Problem Language Result Execution time Memory
310079 2020-10-05T15:33:31 Z mohamedsobhi777 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 2812 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 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 ; 
                update(0 , 1, N , i , x) ; 
        }

        for(int i = 0 ;i < m ; ++ i){
                int t , l , r ; 
                cin >> t >> l >> r ; 
                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:86:25: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   86 |                         if(k > 1) ;
      |                         ^~
sterilizing.cpp:87:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   87 |                                 spray(0 , 1 , N , l , r) ;
      |                                 ^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5093 ms 1820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 640 KB Output is correct
2 Correct 19 ms 1280 KB Output is correct
3 Correct 25 ms 1280 KB Output is correct
4 Correct 68 ms 1016 KB Output is correct
5 Correct 87 ms 2552 KB Output is correct
6 Correct 90 ms 2432 KB Output is correct
7 Execution timed out 5072 ms 2736 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 1656 KB Output is correct
2 Correct 114 ms 1784 KB Output is correct
3 Correct 129 ms 1528 KB Output is correct
4 Correct 143 ms 1528 KB Output is correct
5 Correct 169 ms 2680 KB Output is correct
6 Correct 189 ms 2808 KB Output is correct
7 Correct 158 ms 2680 KB Output is correct
8 Correct 217 ms 2808 KB Output is correct
9 Correct 201 ms 2808 KB Output is correct
10 Correct 226 ms 2812 KB Output is correct
11 Correct 174 ms 2808 KB Output is correct
12 Correct 303 ms 2808 KB Output is correct