oj.uz

Submission #752832

# Submission time Handle Problem Language Result Execution time Memory
752832 2023-06-04T03:19:35 Z Tien_Noob Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1545 ms 9656 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;
        if(v>0) s.insert(i);
        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 212 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 22 ms 468 KB Output is correct
5 Correct 21 ms 596 KB Output is correct
6 Correct 16 ms 596 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 20 ms 596 KB Output is correct
9 Correct 26 ms 576 KB Output is correct
10 Correct 20 ms 596 KB Output is correct
11 Correct 20 ms 648 KB Output is correct
12 Correct 20 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 4412 KB Output is correct
2 Correct 152 ms 3484 KB Output is correct
3 Correct 149 ms 6796 KB Output is correct
4 Correct 211 ms 8120 KB Output is correct
5 Correct 218 ms 8280 KB Output is correct
6 Correct 231 ms 8276 KB Output is correct
7 Correct 217 ms 8240 KB Output is correct
8 Correct 242 ms 8280 KB Output is correct
9 Correct 217 ms 8332 KB Output is correct
10 Correct 222 ms 8228 KB Output is correct
11 Correct 220 ms 8224 KB Output is correct
12 Correct 214 ms 8236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 792 KB Output is correct
2 Correct 52 ms 4028 KB Output is correct
3 Correct 72 ms 4184 KB Output is correct
4 Correct 144 ms 2552 KB Output is correct
5 Correct 221 ms 8212 KB Output is correct
6 Correct 214 ms 8188 KB Output is correct
7 Correct 186 ms 8652 KB Output is correct
8 Correct 210 ms 9132 KB Output is correct
9 Correct 200 ms 9112 KB Output is correct
10 Correct 222 ms 9036 KB Output is correct
11 Correct 196 ms 9088 KB Output is correct
12 Correct 203 ms 9212 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 4808 KB Output is correct
2 Correct 365 ms 5048 KB Output is correct
3 Correct 660 ms 4912 KB Output is correct
4 Correct 451 ms 3408 KB Output is correct
5 Correct 652 ms 9008 KB Output is correct
6 Correct 841 ms 9192 KB Output is correct
7 Correct 630 ms 9392 KB Output is correct
8 Correct 1072 ms 9632 KB Output is correct
9 Correct 903 ms 9656 KB Output is correct
10 Correct 1079 ms 9544 KB Output is correct
11 Correct 666 ms 9488 KB Output is correct
12 Correct 1545 ms 9536 KB Output is correct