oj.uz

Submission #398687

# Submission time Handle Problem Language Result Execution time Memory
398687 2021-05-04T17:45:09 Z Yeboi Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 209 ms 5768 KB 
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
const ll INF = 1000000000;
const ll N = 500005;
const ll MOD = 1000000007;
const ll MAXN = 10000000000;
const ll rootval = 319;
using namespace std;

// segtree with poll updates , spraying function, sum query
// as used in that codeforces SUM AND REPLACE prob idea is after log10 number of divisions element will become 0 so we will check if max of curr seg is >0
// then only apply operation
ll treesum[4*N], treemax[4*N];
ll arr[N];
ll n,k;
void build(ll v, ll tl, ll tr) {
    if (tl == tr) {
        treesum[v] = arr[tl];
        treemax[v] = arr[tl];
    } else {
        ll tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        treesum[v] = treesum[v*2] + treesum[v*2+1];
        treemax[v] = max(treemax[v*2],treemax[v*2+1]);
    }
}
ll sum1(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return treesum[v];
    }
    ll tm = (tl + tr) / 2;
    return sum1(v*2, tl, tm, l, min(r, tm))
           + sum1(v*2+1, tm+1, tr, max(l, tm+1), r);
}
ll sum(ll l, ll r){
    return sum1(1,1,n,l,r);
}   
void update1(ll v, ll tl, ll tr, ll pos, ll new_val) {
    if (tl == tr) {
        treesum[v] = new_val;
        treemax[v] = new_val;
    } else {
        ll tm = (tl + tr) / 2;
        if (pos <= tm)
            update1(v*2, tl, tm, pos, new_val);
        else
            update1(v*2+1, tm+1, tr, pos, new_val);
        treesum[v] = treesum[v*2] + treesum[v*2+1];
        treemax[v] = max(treemax[v],treemax[v*2+1]);
    }
}
void update(ll pos , ll new_val){
    update1(1,1,n,pos,new_val);
    return;
}
void spray_fun(ll v, ll tl, ll tr, ll l, ll r){
    if(tr < l || tl > r){
        return;
    }
    if(tl == tr){
        treesum[v] = treesum[v]/k;
        treemax[v] = treemax[v]/k;
        return;
    }
    if(treemax[v] == 0 || k == 1){
        return;
    }
    ll tm = (tl+tr)/2;
    spray_fun(2*v,tl,tm,l,min(r,tm));
    spray_fun(2*v+1,tm+1,tr,max(l,tm+1),r);
    treesum[v] = treesum[2*v] + treesum[2*v+1];
    treemax[v] = max(treemax[2*v],treemax[2*v+1]);
}
void spray(ll l , ll r){
    spray_fun(1,1,n,l,r);
}
int main(){
    ll q;
    cin >> n >> q >> k;
    f(i,1,n+1){
        ll val;
        cin >> val;
        arr[i] = val;
    }
    build(1,1,n);
    rep(i,q){
        ll s,l,r;
        cin >> s >> l >> r;
        if(s == 1){
            update(l,r);
        }
        else if(s == 2){
            spray(l,r);
        }
        else if(s == 3){
            cout << sum(l,r) << endl;
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3140 KB Output is correct
2 Correct 149 ms 2996 KB Output is correct
3 Correct 130 ms 5188 KB Output is correct
4 Correct 173 ms 5560 KB Output is correct
5 Correct 203 ms 5700 KB Output is correct
6 Correct 201 ms 5684 KB Output is correct
7 Correct 209 ms 5676 KB Output is correct
8 Correct 200 ms 5664 KB Output is correct
9 Correct 195 ms 5768 KB Output is correct
10 Correct 190 ms 5680 KB Output is correct
11 Correct 192 ms 5656 KB Output is correct
12 Correct 192 ms 5680 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 3044 KB Output isn't correct
2 Halted 0 ms 0 KB -