oj.uz

Submission #398686

# Submission time Handle Problem Language Result Execution time Memory
398686 2021-05-04T17:43:57 Z Yeboi Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 213 ms 8212 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] = 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] = 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 332 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 177 ms 5200 KB Output is correct
2 Correct 153 ms 4536 KB Output is correct
3 Correct 133 ms 6980 KB Output is correct
4 Correct 168 ms 7684 KB Output is correct
5 Correct 205 ms 8004 KB Output is correct
6 Correct 202 ms 8120 KB Output is correct
7 Correct 204 ms 8212 KB Output is correct
8 Correct 213 ms 8048 KB Output is correct
9 Correct 196 ms 7876 KB Output is correct
10 Correct 191 ms 7896 KB Output is correct
11 Correct 190 ms 8000 KB Output is correct
12 Correct 195 ms 8016 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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