oj.uz

Submission #558822

# Submission time Handle Problem Language Result Execution time Memory
558822 2022-05-08T13:52:21 Z NintsiChkhaidze Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 244 ms 7364 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define int ll
#define s second
#define f first
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 100005;
int k,mx[4*N],sum[4*N];

void upd(int h,int l,int r,int idx,int val){
    if (l==r){
        sum[h] = val;
        mx[h] = val;
        return;
    } 
    if (idx > (l+r)/2) upd(right,idx,val);
    else upd(left,idx,val);
    
    sum[h] = sum[h*2] + sum[h*2+1];
    mx[h] = max(mx[h*2],mx[h*2+1]);
}
void updseg(int h,int l,int r,int L,int R){
    if (r < L || R < l || mx[h] == 0) return;
    if (l == r){
        sum[h] /= k;
        mx[h] = sum[h];
        return;
    }
    updseg(left,L,R);
    updseg(right,L,R);
    sum[h] = sum[h*2] + sum[h*2+1];
    mx[h] = max(mx[h*2],mx[h*2+1]);
}
int getsum(int h,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return sum[h];
    return getsum(left,L,R) + getsum(right,L,R);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,t;
    cin>>n>>t>>k;
    for (int i=1;i<=n;i++){
        int a;
        cin>>a;
        upd(1,1,n,i,a);
    }
    
    while(t--){
        int tp,l,r;
        cin>>tp>>l>>r;
        if (tp == 1) {
            upd(1,1,n,l,r);
        }else if (tp == 2){
            if (k > 1) updseg(1,1,n,l,r);
        }else{
            cout<<getsum(1,1,n,l,r)<<"\n";
        }
    }
}

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 1 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 472 KB Output is correct
8 Correct 4 ms 544 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 4 ms 464 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4620 KB Output is correct
2 Correct 40 ms 4332 KB Output is correct
3 Correct 43 ms 6340 KB Output is correct
4 Correct 72 ms 6856 KB Output is correct
5 Correct 72 ms 7316 KB Output is correct
6 Correct 67 ms 7264 KB Output is correct
7 Correct 70 ms 7364 KB Output is correct
8 Correct 70 ms 7288 KB Output is correct
9 Correct 63 ms 7176 KB Output is correct
10 Correct 61 ms 7164 KB Output is correct
11 Correct 67 ms 7188 KB Output is correct
12 Correct 68 ms 7184 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 968 KB Output is correct
2 Correct 15 ms 2644 KB Output is correct
3 Correct 25 ms 2780 KB Output is correct
4 Correct 42 ms 2532 KB Output is correct
5 Correct 68 ms 5812 KB Output is correct
6 Correct 69 ms 5828 KB Output is correct
7 Correct 56 ms 6056 KB Output is correct
8 Correct 64 ms 5860 KB Output is correct
9 Correct 76 ms 5716 KB Output is correct
10 Correct 66 ms 5684 KB Output is correct
11 Correct 77 ms 5696 KB Output is correct
12 Correct 56 ms 5712 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4088 KB Output is correct
2 Correct 91 ms 4244 KB Output is correct
3 Correct 118 ms 3648 KB Output is correct
4 Correct 123 ms 3224 KB Output is correct
5 Correct 126 ms 7060 KB Output is correct
6 Correct 146 ms 7140 KB Output is correct
7 Correct 171 ms 7116 KB Output is correct
8 Correct 171 ms 7140 KB Output is correct
9 Correct 165 ms 6984 KB Output is correct
10 Correct 208 ms 7056 KB Output is correct
11 Correct 131 ms 6980 KB Output is correct
12 Correct 244 ms 7004 KB Output is correct