oj.uz

Submission #675969

# Submission time Handle Problem Language Result Execution time Memory
675969 2022-12-28T16:41:14 Z Ronin13 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 3397 ms 14268 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 1e5 + 1;
vector <pll> t(4 * nmax);
vector <ll> T(4 * nmax);
vector <ll> a(nmax);

void build(int v, int l, int r){
    if(l == r){
        t[v] = {a[l], l};
        T[v] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v+ 1, m + 1, r);
    t[v] = max(t[v *2 + 1], t[2 * v]);
    T[v] = T[2 * v] + T[2 * v + 1];
}

void update(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v].f = T[v] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
    T[v] = T[2 * v] + T[2 * v + 1];
}

pll get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return {0, 0};
    if(l >= st && r <= fin)
        return t[v];
    int m = (l + r) /2;
    pll x = get(2 * v, l, m, st, fin);
    pll y = get(2 * v + 1, m + 1, r, st, fin);
    return max(x, y);
}
ll get1(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin)
        return T[v];
    int m = (l + r) /2;
    ll x = get1(2 * v, l, m, st, fin);
    ll y = get1(2 * v + 1, m + 1, r, st, fin);
    return x + y;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q, k; cin >> n >> q >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build(1,1, n);
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int pos, val; cin >> pos >> val;
            update(1, 1, n, pos, val);
            continue;
        }
        if(t == 2){

            vector <pii> vec;
            int l, r; cin >> l >> r;
        if(k == 1) continue;
            while(true){
                pll u = get(1, 1, n, l, r);
                if(!u.f) break;
                u.f /= k;
                update(1, 1, n, u.s, 0);
                vec.pb(u);
            }
            for(auto to : vec)
                update(1, 1, n, to.s, to.f);
            continue;
        }
        if(t == 3){
            int l, r; cin >> l >> r;
            cout << get1(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 13 ms 10452 KB Output is correct
4 Correct 34 ms 10572 KB Output is correct
5 Correct 35 ms 10580 KB Output is correct
6 Correct 25 ms 10580 KB Output is correct
7 Correct 30 ms 10612 KB Output is correct
8 Correct 31 ms 10580 KB Output is correct
9 Correct 41 ms 10604 KB Output is correct
10 Correct 29 ms 10612 KB Output is correct
11 Correct 36 ms 10604 KB Output is correct
12 Correct 34 ms 10584 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 10956 KB Output is correct
2 Correct 44 ms 10908 KB Output is correct
3 Correct 40 ms 10796 KB Output is correct
4 Correct 50 ms 10792 KB Output is correct
5 Correct 63 ms 10956 KB Output is correct
6 Correct 64 ms 10964 KB Output is correct
7 Correct 65 ms 10956 KB Output is correct
8 Correct 74 ms 10948 KB Output is correct
9 Correct 60 ms 10892 KB Output is correct
10 Correct 58 ms 10912 KB Output is correct
11 Correct 56 ms 10888 KB Output is correct
12 Correct 55 ms 10992 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10580 KB Output is correct
2 Correct 33 ms 10908 KB Output is correct
3 Correct 35 ms 11016 KB Output is correct
4 Correct 73 ms 11812 KB Output is correct
5 Correct 108 ms 12124 KB Output is correct
6 Correct 119 ms 12032 KB Output is correct
7 Correct 73 ms 11984 KB Output is correct
8 Correct 113 ms 12320 KB Output is correct
9 Correct 107 ms 11912 KB Output is correct
10 Correct 103 ms 11948 KB Output is correct
11 Correct 104 ms 12020 KB Output is correct
12 Correct 133 ms 11980 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 11648 KB Output is correct
2 Correct 582 ms 11404 KB Output is correct
3 Correct 1235 ms 12076 KB Output is correct
4 Correct 694 ms 11300 KB Output is correct
5 Correct 1048 ms 12528 KB Output is correct
6 Correct 1365 ms 12464 KB Output is correct
7 Correct 1026 ms 13672 KB Output is correct
8 Correct 1985 ms 13896 KB Output is correct
9 Correct 1718 ms 14156 KB Output is correct
10 Correct 2246 ms 14156 KB Output is correct
11 Correct 1264 ms 14268 KB Output is correct
12 Correct 3397 ms 14260 KB Output is correct