oj.uz

Submission #484479

# Submission time Handle Problem Language Result Execution time Memory
484479 2021-11-03T16:17:58 Z Mahdi Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1688 ms 7352 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define F first
#define S second
typedef long long ll;
const int N=1e5+5;
int n, q, k, sz, c[N], mx[3*N];
ll sg[3*N];

void st(int x){
    x+=sz-1;
    sg[x]=c[x-sz+1];
    while(x){
        --x;
        x/=2;
        mx[x]=(c[mx[2*x+1]]<c[mx[2*x+2]]? mx[2*x+2] : mx[2*x+1]);
        sg[x]=sg[2*x+1]+sg[2*x+2];
    }
}

ll sum(int x, int lx, int rx, int l, int r){
    if(lx>=r || rx<=l)
        return 0;
    if(lx>=l && rx<=r)
        return sg[x];
    int m=(lx+rx)/2;
    return sum(2*x+1, lx, m, l, r)+sum(2*x+2, m, rx, l, r);
}

int seg(int x, int lx, int rx, int l, int r){
    if(lx>=r || rx<=l)
        return n;
    if(lx>=l && rx<=r)
        return mx[x];
    int m=(lx+rx)/2;
    int L=seg(2*x+1, lx, m, l, r), R=seg(2*x+2, m, rx, l, r);
    return (c[L]<c[R] ? R : L);
}

void opr(int l, int r){
    if(k==1)
        return;
    vector<pii>v;
    int z=seg(0, 0, sz, l, r);
    while(c[z]){
        v.push_back({z, c[z]/k});
        c[z]=0;
        st(z);
        z=seg(0, 0, sz, l, r);
    }
    for(auto u:v){
        c[u.F]=u.S;
        st(u.F);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q>>k;
    for(int i=0;i<n;++i)
        cin>>c[i];
    sz=1;
    while(sz<n)
        sz<<=1;
    iota(mx+sz-1, mx+sz+n-1, 0);
    for(int i=sz-1;i<sz+n-1;++i)
        sg[i]=c[i-sz+1];
    for(int i=sz-2;i>=0;--i){
        sg[i]=sg[2*i+1]+sg[2*i+2];
        mx[i]=(c[mx[2*i+1]]<c[mx[2*i+2]] ? mx[2*i+2] : mx[2*i+1]);
    }
    int s, t, u;
    while(q--){
        cin>>s>>t>>u;
        if(s==1){
            c[--t]=u;
            st(t);
        }
        else if(s==2)
            opr(--t, u);
        else
            cout<<sum(0, 0, sz, --t, u)<<'\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 16 ms 380 KB Output is correct
5 Correct 16 ms 484 KB Output is correct
6 Correct 11 ms 460 KB Output is correct
7 Correct 15 ms 460 KB Output is correct
8 Correct 15 ms 480 KB Output is correct
9 Correct 21 ms 460 KB Output is correct
10 Correct 17 ms 460 KB Output is correct
11 Correct 14 ms 460 KB Output is correct
12 Correct 15 ms 480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3524 KB Output is correct
2 Correct 39 ms 3544 KB Output is correct
3 Correct 34 ms 4956 KB Output is correct
4 Correct 45 ms 5796 KB Output is correct
5 Correct 54 ms 6276 KB Output is correct
6 Correct 61 ms 6248 KB Output is correct
7 Correct 50 ms 6316 KB Output is correct
8 Correct 54 ms 6260 KB Output is correct
9 Correct 47 ms 6192 KB Output is correct
10 Correct 47 ms 6204 KB Output is correct
11 Correct 48 ms 6116 KB Output is correct
12 Correct 50 ms 6156 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 588 KB Output is correct
2 Correct 17 ms 1868 KB Output is correct
3 Correct 23 ms 2292 KB Output is correct
4 Correct 53 ms 2444 KB Output is correct
5 Correct 73 ms 4968 KB Output is correct
6 Correct 74 ms 5028 KB Output is correct
7 Correct 40 ms 4932 KB Output is correct
8 Correct 85 ms 5140 KB Output is correct
9 Correct 67 ms 4820 KB Output is correct
10 Correct 68 ms 4808 KB Output is correct
11 Correct 68 ms 4784 KB Output is correct
12 Correct 70 ms 4864 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 3340 KB Output is correct
2 Correct 302 ms 3944 KB Output is correct
3 Correct 645 ms 3628 KB Output is correct
4 Correct 369 ms 3360 KB Output is correct
5 Correct 554 ms 6572 KB Output is correct
6 Correct 714 ms 6672 KB Output is correct
7 Correct 517 ms 7224 KB Output is correct
8 Correct 1018 ms 7352 KB Output is correct
9 Correct 874 ms 6344 KB Output is correct
10 Correct 1097 ms 7212 KB Output is correct
11 Correct 699 ms 6340 KB Output is correct
12 Correct 1688 ms 7024 KB Output is correct