oj.uz

Submission #675967

# Submission time Handle Problem Language Result Execution time Memory
675967 2022-12-28T16:38:37 Z Ronin13 Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 3295 ms 14400 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], 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 10532 KB Output is correct
4 Correct 35 ms 10548 KB Output is correct
5 Correct 35 ms 10680 KB Output is correct
6 Correct 31 ms 10528 KB Output is correct
7 Correct 30 ms 10680 KB Output is correct
8 Correct 31 ms 10664 KB Output is correct
9 Correct 41 ms 10780 KB Output is correct
10 Correct 29 ms 10672 KB Output is correct
11 Correct 29 ms 10664 KB Output is correct
12 Correct 32 ms 10580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11548 KB Output is correct
2 Correct 44 ms 12468 KB Output is correct
3 Correct 42 ms 12416 KB Output is correct
4 Correct 51 ms 12916 KB Output is correct
5 Correct 61 ms 13388 KB Output is correct
6 Correct 68 ms 13424 KB Output is correct
7 Correct 67 ms 13328 KB Output is correct
8 Correct 61 ms 13428 KB Output is correct
9 Correct 56 ms 13260 KB Output is correct
10 Correct 57 ms 13280 KB Output is correct
11 Correct 57 ms 13316 KB Output is correct
12 Correct 60 ms 13224 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 11924 KB Output is correct
2 Correct 546 ms 11704 KB Output is correct
3 Correct 1196 ms 12312 KB Output is correct
4 Correct 676 ms 11644 KB Output is correct
5 Correct 990 ms 12544 KB Output is correct
6 Correct 1298 ms 12468 KB Output is correct
7 Correct 929 ms 13704 KB Output is correct
8 Correct 1876 ms 13968 KB Output is correct
9 Correct 1651 ms 14268 KB Output is correct
10 Correct 2071 ms 14264 KB Output is correct
11 Correct 1196 ms 14400 KB Output is correct
12 Correct 3295 ms 14216 KB Output is correct