oj.uz

Submission #31837

# Submission time Handle Problem Language Result Execution time Memory
31837 2017-09-11T03:47:11 Z Dat160601 Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 799 ms 12332 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q,k,x,y;
long long a[100007],it[400007],mx[400007],lazy[400007];
void init(int p,int l,int r){
    if(l==r){
        it[p]=a[l];
        mx[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    init(p*2,l,mid);
    init(p*2+1,mid+1,r);
    it[p]=it[p*2]+it[p*2+1];
    mx[p]=max(mx[p*2],mx[p*2+1]);
}
void dolazy(int p,int l,int r){
    if(lazy[p]==0) return;
    it[p]=0;
    mx[p]=0;
    if(l!=r){
        lazy[p*2]=1;
        lazy[p*2+1]=1;
    }
    lazy[p]=0;
}
void upd(int p,int l,int r,int pos,int val){
    dolazy(p,l,r);
    if(l>pos || r<pos) return;
    if(l==pos && l==r){
        it[p]=val;
        mx[p]=val;
        return;
    }
    int mid=(l+r)/2;
    upd(p*2,l,mid,pos,val);
    upd(p*2+1,mid+1,r,pos,val);
    it[p]=it[p*2]+it[p*2+1];
    mx[p]=max(mx[p*2],mx[p*2+1]);
}
void div(int p,int l,int r,int L,int R){
    dolazy(p,l,r);
    if(l>R || r<L || l>r) return;
    if(l>=L && r<=R && mx[p]<=1 && k==1) return;
    if(l>=L && r<=R && mx[p]<k){
        if(mx[p]==0) return;
        it[p]=0;
        mx[p]=0;
        if(l!=r){
            lazy[p*2]=1;
            lazy[p*2+1]=1;
        }
        return;
    }
    if(l==r){
        it[p]=it[p]/k;
        mx[p]=mx[p]/k;
        return;
    }
    int mid=(l+r)/2;
    div(p*2,l,mid,L,R);
    div(p*2+1,mid+1,r,L,R);
    it[p]=it[p*2]+it[p*2+1];
    mx[p]=max(mx[p*2],mx[p*2+1]);
}
long long get(int p,int l,int r,int L,int R){
    dolazy(p,l,r);
    if(l>R || r<L || l>r) return 0;
    if(l>=L && r<=R){
        //cout<<l<<" "<<r<<" "<<it[p]<<endl;
        return it[p];
    }
    int mid=(l+r)/2;
    return (get(p*2,l,mid,L,R)+get(p*2+1,mid+1,r,L,R));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init(1,1,n);
    int type;
    for(int i=1;i<=q;i++){
        cin>>type>>x>>y;
        if(type==1){
            upd(1,1,n,x,y);
        }
        else if(type==2){
            div(1,1,n,x,y);
        }
        else{
            cout<<get(1,1,n,x,y)<<"\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12332 KB Output is correct
2 Correct 6 ms 12332 KB Output is correct
3 Correct 0 ms 12332 KB Output is correct
4 Correct 6 ms 12332 KB Output is correct
5 Correct 3 ms 12332 KB Output is correct
6 Correct 9 ms 12332 KB Output is correct
7 Correct 3 ms 12332 KB Output is correct
8 Correct 9 ms 12332 KB Output is correct
9 Correct 6 ms 12332 KB Output is correct
10 Correct 9 ms 12332 KB Output is correct
11 Correct 9 ms 12332 KB Output is correct
12 Correct 6 ms 12332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 0 KB -1: Interrupted system call
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 12332 KB Output is correct
2 Correct 69 ms 12332 KB Output is correct
3 Correct 46 ms 12332 KB Output is correct
4 Correct 243 ms 12332 KB Output is correct
5 Correct 389 ms 12332 KB Output is correct
6 Correct 206 ms 12332 KB Output is correct
7 Correct 256 ms 12332 KB Output is correct
8 Correct 393 ms 12332 KB Output is correct
9 Correct 316 ms 12332 KB Output is correct
10 Correct 199 ms 12332 KB Output is correct
11 Correct 206 ms 12332 KB Output is correct
12 Correct 149 ms 12332 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 12332 KB Output is correct
2 Correct 366 ms 12332 KB Output is correct
3 Correct 413 ms 12332 KB Output is correct
4 Correct 513 ms 12332 KB Output is correct
5 Correct 523 ms 12332 KB Output is correct
6 Correct 436 ms 12332 KB Output is correct
7 Correct 619 ms 12332 KB Output is correct
8 Correct 759 ms 12332 KB Output is correct
9 Correct 503 ms 12332 KB Output is correct
10 Correct 433 ms 12332 KB Output is correct
11 Correct 403 ms 12332 KB Output is correct
12 Correct 799 ms 12332 KB Output is correct