oj.uz

Submission #1101032

# Submission time Handle Problem Language Result Execution time Memory
1101032 2024-10-15T11:12:26 Z tsengang Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 150 ms 4792 KB 
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;
struct segtree{
    int n;
    vector<ll>d;
    segtree(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)/2;
        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 0;
        if(L<=l&&r<=R){
            return d[v];
        }
        ll m=(l+r)/2;
        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)/2;
        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];
    }
};
int main() {
    ll n,q,k;
    cin >> n >> q >> k;
    ll a[n+2];
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
    }
    if(n <= 3000 && q <= 3000){
        while(q--){
            ll s,x,y;
            cin >> s >> x >> y;
            if(s == 1){
                a[x] = y;
            }
            if(s == 2){
                for(ll i = x; i <= y; i++)a[i] /= k;
            }
            if(s == 3){
                ll sum = 0;
                for(ll i = x; i <= y; i++){
                    sum+=a[i];
                }
                cout << sum << '\n';
            }
        }
        return 0;
    }
    if(k == 1){
        segtree gang(n);
        for(ll i = 1 ; i <= n; i++){
            gang.update(1,1,n,i,a[i]);
        }
        while(q--){
            ll s,x,y;
            cin >> s >> x >> y;
            if(s == 1){
                gang.update(1,1,n,x,y);
            }
            if(s == 3){
                cout << gang.query(1,1,n,x,y) << '\n';
            }
        }
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 2636 KB Output is correct
2 Correct 102 ms 2120 KB Output is correct
3 Correct 88 ms 3656 KB Output is correct
4 Correct 113 ms 4548 KB Output is correct
5 Correct 134 ms 4680 KB Output is correct
6 Correct 142 ms 4792 KB Output is correct
7 Correct 150 ms 4680 KB Output is correct
8 Correct 135 ms 4784 KB Output is correct
9 Correct 132 ms 4680 KB Output is correct
10 Correct 130 ms 4784 KB Output is correct
11 Correct 130 ms 4688 KB Output is correct
12 Correct 134 ms 4680 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 756 KB Output isn't correct
2 Halted 0 ms 0 KB -