oj.uz

Submission #1101033

# Submission time Handle Problem Language Result Execution time Memory
1101033 2024-10-15T11:13:40 Z tsengang Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 143 ms 4788 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];
    }
    assert(k==1);
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2648 KB Output is correct
2 Correct 101 ms 2120 KB Output is correct
3 Correct 87 ms 3656 KB Output is correct
4 Correct 110 ms 4424 KB Output is correct
5 Correct 133 ms 4688 KB Output is correct
6 Correct 135 ms 4616 KB Output is correct
7 Correct 132 ms 4692 KB Output is correct
8 Correct 133 ms 4788 KB Output is correct
9 Correct 131 ms 4680 KB Output is correct
10 Correct 130 ms 4680 KB Output is correct
11 Correct 134 ms 4680 KB Output is correct
12 Correct 143 ms 4680 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 1360 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -