oj.uz

Submission #204487

# Submission time Handle Problem Language Result Execution time Memory
204487 2020-02-26T02:38:47 Z aloo123 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 363 ms 8184 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
using namespace std;

const ll N = 1e5+5;
const ll MOD = 1e9+7;
ll tree[4LL*N];


ll a[N];
ll k;
ll ma[4LL*N];
ll LOG(ll n){
    ll ans = 0;
    while(n){
        ans += 1;
        n /= k;
    }
    return ans;
}
void merge(ll node){
    tree[node] = tree[node*2] + tree[node*2+1];
    ma[node] = max(ma[node*2],ma[node*2+1]);
}

void build(ll node,ll l,ll r){
    if(l==r){
        tree[node] = a[l];
        ma[node] = a[l];
    }
    else{
        ll mid = (l+r)/2;
        build(node * 2,l,mid);
        build(node * 2 + 1,mid+1,r);
        merge(node);
    }
}

void update(ll node,ll l,ll r,ll idx,ll val){
    if(l == r){
        tree[node] = val;
        ma[node] = val;
    }
    else{
        ll mid = (l+r)/2;
        if(idx <= mid) update(node * 2,l,mid,idx,val);
        else update(node * 2 +1,mid+1,r,idx,val);
        merge(node);
    }
}

void update2(ll node,ll l,ll r,ll st,ll en){
     if(l > en || r < st) return ;
     if(l >= st && r<=en){
        if(ma[node] == 0) return;
         if(l == r){
             
             tree[node] /= k;
             ma[node] /= k;
            return;
         }}
    ll mid = (l+r)/2;
    update2(node*2,l,mid,st,en);
    update2(node*2+1,mid+1,r,st,en);
    merge(node);
}

ll query(ll node,ll l,ll r,ll st,ll en){
    if(l > en || r < st) return 0;
    if(l >= st && r<=en) return tree[node];
    ll mid =(l+r)/2;
    ll p1 = query(node*2,l,mid,st,en);
    ll p2 = query(node*2+1,mid+1,r,st,en);
    return p1 +p2;
}

int main()
{


    ios_base::sync_with_stdio(0);
    cin.tie(0);


    ll n,q;
    cin >> n >> q >> k;


    for(int i = 1;i<=n;i++) cin >> a[i];
    build(1,1,n);
    while(q--){
        ll t,l,r;
        cin>> t>> l >> r;
        if(t == 1){
            update(1,1,n,l,r);
        }
        else if(t==2){
            if(k != 1)
            update2(1,1,n,l,r);
        }
        else{
            cout << query(1,1,n,l,r) << endl;
        }
    }


    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 11 ms 504 KB Output is correct
5 Correct 11 ms 632 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 10 ms 632 KB Output is correct
9 Correct 11 ms 632 KB Output is correct
10 Correct 13 ms 632 KB Output is correct
11 Correct 11 ms 632 KB Output is correct
12 Correct 11 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 5112 KB Output is correct
2 Correct 121 ms 4728 KB Output is correct
3 Correct 96 ms 7032 KB Output is correct
4 Correct 120 ms 7800 KB Output is correct
5 Correct 145 ms 8184 KB Output is correct
6 Correct 151 ms 8180 KB Output is correct
7 Correct 152 ms 8184 KB Output is correct
8 Correct 154 ms 8184 KB Output is correct
9 Correct 142 ms 8056 KB Output is correct
10 Correct 141 ms 8056 KB Output is correct
11 Correct 140 ms 8184 KB Output is correct
12 Correct 138 ms 8056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1144 KB Output is correct
2 Correct 31 ms 3068 KB Output is correct
3 Correct 43 ms 3192 KB Output is correct
4 Correct 133 ms 2808 KB Output is correct
5 Correct 150 ms 6776 KB Output is correct
6 Correct 169 ms 6896 KB Output is correct
7 Correct 133 ms 6904 KB Output is correct
8 Correct 157 ms 6904 KB Output is correct
9 Correct 147 ms 6520 KB Output is correct
10 Correct 142 ms 6520 KB Output is correct
11 Correct 143 ms 6712 KB Output is correct
12 Correct 150 ms 6520 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 4600 KB Output is correct
2 Correct 168 ms 4728 KB Output is correct
3 Correct 165 ms 4052 KB Output is correct
4 Correct 210 ms 3588 KB Output is correct
5 Correct 249 ms 8040 KB Output is correct
6 Correct 265 ms 8056 KB Output is correct
7 Correct 242 ms 8036 KB Output is correct
8 Correct 301 ms 7928 KB Output is correct
9 Correct 269 ms 7928 KB Output is correct
10 Correct 296 ms 7928 KB Output is correct
11 Correct 245 ms 7932 KB Output is correct
12 Correct 363 ms 7928 KB Output is correct