oj.uz

Submission #398689

# Submission time Handle Problem Language Result Execution time Memory
398689 2021-05-04T17:46:07 Z Yeboi Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 503 ms 7996 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*2],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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 452 KB Output is correct
5 Correct 13 ms 556 KB Output is correct
6 Correct 8 ms 524 KB Output is correct
7 Correct 9 ms 460 KB Output is correct
8 Correct 9 ms 460 KB Output is correct
9 Correct 10 ms 520 KB Output is correct
10 Correct 8 ms 460 KB Output is correct
11 Correct 8 ms 512 KB Output is correct
12 Correct 9 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 3188 KB Output is correct
2 Correct 148 ms 2980 KB Output is correct
3 Correct 131 ms 5280 KB Output is correct
4 Correct 170 ms 5652 KB Output is correct
5 Correct 202 ms 5724 KB Output is correct
6 Correct 201 ms 5700 KB Output is correct
7 Correct 201 ms 5728 KB Output is correct
8 Correct 202 ms 5572 KB Output is correct
9 Correct 195 ms 5572 KB Output is correct
10 Correct 193 ms 5616 KB Output is correct
11 Correct 195 ms 5572 KB Output is correct
12 Correct 196 ms 5680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 620 KB Output is correct
2 Correct 33 ms 2892 KB Output is correct
3 Correct 47 ms 3116 KB Output is correct
4 Correct 149 ms 2804 KB Output is correct
5 Correct 178 ms 6596 KB Output is correct
6 Correct 179 ms 6632 KB Output is correct
7 Correct 165 ms 6760 KB Output is correct
8 Correct 181 ms 6744 KB Output is correct
9 Correct 165 ms 6472 KB Output is correct
10 Correct 169 ms 6464 KB Output is correct
11 Correct 167 ms 6460 KB Output is correct
12 Correct 169 ms 6516 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 2948 KB Output is correct
2 Correct 213 ms 4672 KB Output is correct
3 Correct 201 ms 3912 KB Output is correct
4 Correct 258 ms 3524 KB Output is correct
5 Correct 297 ms 7836 KB Output is correct
6 Correct 323 ms 7920 KB Output is correct
7 Correct 296 ms 7996 KB Output is correct
8 Correct 374 ms 7892 KB Output is correct
9 Correct 358 ms 7748 KB Output is correct
10 Correct 386 ms 7748 KB Output is correct
11 Correct 316 ms 7868 KB Output is correct
12 Correct 503 ms 7816 KB Output is correct