oj.uz

Submission #1101031

# Submission time Handle Problem Language Result Execution time Memory
1101031 2024-10-15T11:12:04 Z tsengang Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 186 ms 7248 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
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 2632 KB Output is correct
2 Correct 157 ms 3664 KB Output is correct
3 Correct 116 ms 5360 KB Output is correct
4 Correct 133 ms 6736 KB Output is correct
5 Correct 151 ms 7244 KB Output is correct
6 Correct 186 ms 7244 KB Output is correct
7 Correct 151 ms 7080 KB Output is correct
8 Correct 145 ms 7248 KB Output is correct
9 Correct 144 ms 7080 KB Output is correct
10 Correct 144 ms 6996 KB Output is correct
11 Correct 146 ms 6956 KB Output is correct
12 Correct 162 ms 6984 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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