oj.uz

Submission #1101260

# Submission time Handle Problem Language Result Execution time Memory
1101260 2024-10-16T01:03:01 Z tsengang Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 7240 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];
    }
    void updater(ll node, ll L, ll R, ll l, ll r, ll val){
    if (L > R || L > r || R < l)
        return;
    if (L == R){
        d[node] /= val;
        return;
    }
    ll mid = (L + R) / 2;
    updater(node*2, L, mid, l, r, val);
    updater(node*2 + 1, mid + 1, R, l, r, val);
    d[node] = d[node*2] + d[node*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];
    }
    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 == 2){
            if(k == 1) continue;
            gang.updater(1,1,n,x,y,k);
        }
        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 4 ms 336 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 9 ms 592 KB Output is correct
6 Correct 10 ms 624 KB Output is correct
7 Correct 9 ms 592 KB Output is correct
8 Correct 9 ms 764 KB Output is correct
9 Correct 10 ms 592 KB Output is correct
10 Correct 10 ms 624 KB Output is correct
11 Correct 14 ms 592 KB Output is correct
12 Correct 9 ms 592 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4680 KB Output is correct
2 Correct 120 ms 3656 KB Output is correct
3 Correct 95 ms 5332 KB Output is correct
4 Correct 124 ms 6728 KB Output is correct
5 Correct 148 ms 7240 KB Output is correct
6 Correct 149 ms 7240 KB Output is correct
7 Correct 138 ms 7240 KB Output is correct
8 Correct 138 ms 7092 KB Output is correct
9 Correct 133 ms 6908 KB Output is correct
10 Correct 133 ms 7080 KB Output is correct
11 Correct 133 ms 6948 KB Output is correct
12 Correct 134 ms 6992 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1096 KB Output is correct
2 Correct 345 ms 2388 KB Output is correct
3 Correct 594 ms 2552 KB Output is correct
4 Correct 1104 ms 2444 KB Output is correct
5 Correct 4339 ms 5824 KB Output is correct
6 Correct 4282 ms 5772 KB Output is correct
7 Correct 119 ms 5708 KB Output is correct
8 Correct 4374 ms 5780 KB Output is correct
9 Execution timed out 5057 ms 4988 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 4064 KB Output is correct
2 Correct 2302 ms 4204 KB Output is correct
3 Correct 1098 ms 3380 KB Output is correct
4 Correct 1328 ms 3476 KB Output is correct
5 Correct 4329 ms 6988 KB Output is correct
6 Correct 4367 ms 7056 KB Output is correct
7 Correct 4438 ms 6964 KB Output is correct
8 Correct 4348 ms 6912 KB Output is correct
9 Execution timed out 5060 ms 5952 KB Time limit exceeded
10 Halted 0 ms 0 KB -