oj.uz

Submission #310078

# Submission time Handle Problem Language Result Execution time Memory
310078 2020-10-05T15:28:46 Z mohamedsobhi777 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 5144 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 = 1e5 + 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 3 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 4 ms 512 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 512 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 4 ms 512 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5035 ms 2024 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 512 KB Output is correct
2 Correct 18 ms 1280 KB Output is correct
3 Correct 26 ms 1280 KB Output is correct
4 Correct 62 ms 896 KB Output is correct
5 Correct 85 ms 2432 KB Output is correct
6 Correct 84 ms 2432 KB Output is correct
7 Execution timed out 5083 ms 2444 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 110 ms 3324 KB Output is correct
3 Correct 124 ms 2636 KB Output is correct
4 Correct 145 ms 3192 KB Output is correct
5 Correct 172 ms 5116 KB Output is correct
6 Correct 184 ms 5112 KB Output is correct
7 Correct 164 ms 5144 KB Output is correct
8 Correct 214 ms 5112 KB Output is correct
9 Correct 201 ms 5048 KB Output is correct
10 Correct 231 ms 5112 KB Output is correct
11 Correct 171 ms 4984 KB Output is correct
12 Correct 313 ms 5112 KB Output is correct