oj.uz

Submission #752831

# Submission time Handle Problem Language Result Execution time Memory
752831 2023-06-04T03:13:58 Z Tien_Noob Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 300 ms 9616 KB 
#include <bits/stdc++.h>
#define ll long long
#define sp << " "
#define faster ios_base::sync_with_stdio(0); cin.tie(0);  .tie(0);
using namespace std;
ll n, q, k, a[100005], t, l, r;
set<ll>::iterator il, ir;
ll st[400005], tmp;
set<ll> s;
bool still;
vector<ll> v;

void update(ll id, ll l , ll r, ll i, ll v){
    if(i<l||r<i) return ;
    if(l==r){
        st[id]=v;
        return ;
    }
    ll mid=(l+r)/2;
    update(id*2,l,mid,i,v);
    update(id*2+1,mid+1,r,i,v);
    st[id]=st[id*2]+st[id*2+1];
}

void update_divk(ll id, ll l , ll r, ll i){
    if(i<l||r<i) return ;
    if(l==r){
        st[id]=st[id]/k;
        if(st[id]>0) still=true;
        return ;
    }
    ll mid=(l+r)/2;
    update_divk(id*2,l,mid,i);
    update_divk(id*2+1,mid+1,r,i);
    st[id]=st[id*2]+st[id*2+1];
}

ll getsum(ll id, ll l, ll r, ll u, ll v){
    if(v<l||r<u) return 0;
    if(u<=l&&r<=v) return st[id];
    ll mid=(l+r)/2;
    return getsum(id*2,l,mid,u,v)+getsum(id*2+1,mid+1,r,u,v);
}
int main(){
    //faster;
    cin >> n >> q >> k;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i]>=0) s.insert(i);
        update(1,1,n,i,a[i]);
    }
    while(q--){
        cin >> t >> l >> r;
        if(t==1) update(1,1,n,l,r);
        else if(t==2&&k!=1){
            while(true){
                il = s.lower_bound(l);
                if(il==s.end()||*il>r){
                    break;
                }
                still=false;
                update_divk(1,1,n,*il);
                if(still) v.push_back(*il);
                s.erase(*il);
            }
            while(v.size()>0){
                s.insert(v.back());
                v.pop_back();
            }
        }
        else if(t==3) cout << getsum(1,1,n,l,r) << "\n";
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 340 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 159 ms 5208 KB Output is correct
2 Correct 130 ms 4824 KB Output is correct
3 Correct 132 ms 8056 KB Output is correct
4 Correct 174 ms 9336 KB Output is correct
5 Correct 197 ms 9548 KB Output is correct
6 Correct 237 ms 9580 KB Output is correct
7 Correct 201 ms 9616 KB Output is correct
8 Correct 203 ms 9536 KB Output is correct
9 Correct 200 ms 9484 KB Output is correct
10 Correct 195 ms 9500 KB Output is correct
11 Correct 190 ms 9552 KB Output is correct
12 Correct 194 ms 9580 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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