oj.uz

Submission #1100606

# Submission time Handle Problem Language Result Execution time Memory
1100606 2024-10-14T10:22:15 Z irmuun Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 766 ms 12000 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

ll n,q,k;

struct segtree{
    vector<ll>d;
    void init(ll n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll v,ll l,ll r){
        if(l==r){
            d[v]=0;
            return;
        }
        ll m=(l+r)>>1;
        build(v*2,l,m);
        build(v*2+1,m+1,r);
        d[v]=d[v*2]+d[v*2+1];
    }
    ll query(ll v,ll l,ll r,ll L,ll R){
        if(L>R||l>R||L>r) return 0ll;
        if(L<=l&&r<=R){
            return d[v];
        }
        ll m=(l+r)>>1;
        return query(v*2,l,m,L,R)+query(v*2+1,m+1,r,L,R);
    }
    void update(ll v,ll l,ll r,ll pos,ll val){
        if(pos<l||r<pos) return;
        if(l==r){
            d[v]=val;
            return;
        }
        ll m=(l+r)>>1;
        update(v*2,l,m,pos,val);
        update(v*2+1,m+1,r,pos,val);
        d[v]=d[v*2]+d[v*2+1];
    }
    void update2(ll v,ll l,ll r,ll pos){
        if(pos<l||r<pos) return;
        if(l==r){
            d[v]/=k;
            return;
        }
        ll m=(l+r)>>1;
        update2(v*2,l,m,pos);
        update2(v*2+1,m+1,r,pos);
        d[v]=d[v*2]+d[v*2+1];
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q>>k;
    segtree sg;
    sg.init(n);
    ll c[n+5];
    set<ll>st;
    for(ll i=1;i<=n;i++){
        cin>>c[i];
        sg.update(1,1,n,i,c[i]);
        if(c[i]>0){
            st.insert(i);
        }
    }
    if(k==1){
        for(ll j=1;j<=q;j++){
            ll s,t,u;
            cin>>s>>t>>u;
            if(s==1){
                sg.update(1,1,n,t,u);
            }
            if(s==3){
                cout<<sg.query(1,1,n,t,u)<<"\n";
            }
        }
        return 0;
    }
    for(ll j=1;j<=q;j++){
        ll s,t,u;
        cin>>s>>t>>u;
        if(s==1){
            sg.update(1,1,n,t,u);
            if(u>0){
                st.insert(t);
            }
        }
        if(s==2){
            ll cur=t,i;
            while(!st.empty()){
                auto it=st.lower_bound(cur);
                if(it==st.end()||*it>u) break;
                ll i=*it;
                sg.update2(1,1,n,i);
                if(sg.query(1,1,n,i,i)==0){
                    st.erase(i);
                }
                cur=*it+1;
            }
        }
        if(s==3){
            cout<<sg.query(1,1,n,t,u)<<"\n";
        }
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:99:22: warning: unused variable 'i' [-Wunused-variable]
   99 |             ll cur=t,i;
      |                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 13 ms 596 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 9 ms 780 KB Output is correct
8 Correct 9 ms 596 KB Output is correct
9 Correct 11 ms 792 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 9 ms 596 KB Output is correct
12 Correct 9 ms 848 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6988 KB Output is correct
2 Correct 35 ms 5204 KB Output is correct
3 Correct 43 ms 9036 KB Output is correct
4 Correct 52 ms 11340 KB Output is correct
5 Correct 64 ms 11852 KB Output is correct
6 Correct 60 ms 12000 KB Output is correct
7 Correct 74 ms 11852 KB Output is correct
8 Correct 66 ms 11904 KB Output is correct
9 Correct 59 ms 11852 KB Output is correct
10 Correct 56 ms 11852 KB Output is correct
11 Correct 61 ms 11832 KB Output is correct
12 Correct 57 ms 11872 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1120 KB Output is correct
2 Correct 20 ms 3412 KB Output is correct
3 Correct 23 ms 3660 KB Output is correct
4 Correct 39 ms 3148 KB Output is correct
5 Correct 69 ms 8100 KB Output is correct
6 Correct 67 ms 8012 KB Output is correct
7 Correct 51 ms 8268 KB Output is correct
8 Correct 67 ms 8192 KB Output is correct
9 Correct 65 ms 8020 KB Output is correct
10 Correct 61 ms 8012 KB Output is correct
11 Correct 63 ms 7856 KB Output is correct
12 Correct 60 ms 8012 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 6520 KB Output is correct
2 Correct 162 ms 6720 KB Output is correct
3 Correct 297 ms 5452 KB Output is correct
4 Correct 197 ms 4996 KB Output is correct
5 Correct 300 ms 11736 KB Output is correct
6 Correct 410 ms 11736 KB Output is correct
7 Correct 286 ms 11596 KB Output is correct
8 Correct 507 ms 11596 KB Output is correct
9 Correct 413 ms 11476 KB Output is correct
10 Correct 498 ms 11596 KB Output is correct
11 Correct 345 ms 11596 KB Output is correct
12 Correct 766 ms 11596 KB Output is correct