oj.uz

Submission #477537

# Submission time Handle Problem Language Result Execution time Memory
477537 2021-10-02T13:39:49 Z ocarima Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 580 ms 61012 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define lli long long int
#define nl "\n"
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b){ cout << x[i] << ", "; } cout << "]" << nl

#define MAXN 600000
#define MAXPOT 32
#define actplaca 1
#define aerosol 2
#define obtensuma 3

lli n, q, k, maxpot, tmp, tipo, l, r, offset, st[MAXPOT][MAXN], lazy[MAXN];
lli cnt;

void llena(lli nodo, lli x){
    if (k == 1){
        st[0][nodo] = x;
        return;
    }
    lli pot = 0;
    while(x){
        st[pot][nodo] = x;
        x /= k;
        ++pot;
    }
    while(pot <= maxpot) st[pot++][nodo] = 0;
}

void mezcla(lli nodo, lli a, lli b){
    rep(i, 0, maxpot) st[i][nodo] = st[i][a] + st[i][b];
}

void divide(lli nodo, lli veces){
    rep(i, veces, maxpot) st[i - veces][nodo] = st[i][nodo];
    rep(i, max(0ll, maxpot - veces + 1), maxpot) st[i][nodo] = 0;
}

void push(lli nodo, lli s, lli e){
    if (lazy[nodo]){
        divide(nodo, lazy[nodo]);
        if (nodo < offset){
            lazy[nodo * 2] += lazy[nodo];
            lazy[nodo * 2 + 1] += lazy[nodo];
        }
    }
    lazy[nodo] = 0;
}

void actvalor(lli nodo, lli s, lli e, lli pos, lli val){
    push(nodo, s, e);
    if (s > pos || e < pos) return;
    if (s == pos && e == pos){
        llena(nodo, val);
        return;
    }
    lli mitad = (s + e) / 2;
    actvalor(nodo * 2, s, mitad, pos, val);
    actvalor(nodo * 2 + 1, mitad + 1, e, pos, val);
    mezcla(nodo, nodo * 2, nodo * 2 + 1);
}

void actrango(lli nodo, lli s, lli e, lli l, lli r){
    push(nodo, s, e);
    if (s > r || e < l) return;
    if (s >= l && e <= r){
        lazy[nodo]++;
        push(nodo, s, e);
        return;
    }
    lli mitad = (s + e) / 2;
    actrango(nodo * 2, s, mitad, l, r);
    actrango(nodo * 2 + 1, mitad + 1, e, l, r);
    mezcla(nodo, nodo * 2, nodo * 2 + 1);
}

lli qryrango(lli nodo, lli s, lli e, lli l, lli r){
    push(nodo, s, e);
    if (s > r || e < l) return 0;
    if (s >= l && e <= r) return st[0][nodo];
    lli mitad = (s + e) / 2;
    return qryrango(nodo * 2, s, mitad, l, r) + qryrango(nodo * 2 + 1, mitad + 1, e, l, r);
}

int main()
{
    fastio;
    cin >> n >> q >> k;
    offset = 1;
    while(offset < n) offset <<= 1;

    maxpot = 0;
    tmp = 1e9 + 1;
    while(tmp && k > 1){
        ++maxpot;
        tmp /= k;
    }

    rep(i, 1, n){
        cin >> tmp;
        llena(offset + i - 1, tmp);
    }

    repa(i, offset - 1, 1) mezcla(i, i * 2, i * 2 + 1);

    while(q--){
        cin >> tipo >> l >> r;
        if (tipo == actplaca) actvalor(1, 1, offset, l, r);
        else if (tipo == aerosol && k > 1) actrango(1, 1, offset, l, r);
        else if (tipo == obtensuma) cout << qryrango(1, 1, offset, l, r) << nl;
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 6 ms 1488 KB Output is correct
5 Correct 6 ms 1392 KB Output is correct
6 Correct 5 ms 1104 KB Output is correct
7 Correct 5 ms 1240 KB Output is correct
8 Correct 5 ms 1232 KB Output is correct
9 Correct 7 ms 1612 KB Output is correct
10 Correct 6 ms 1232 KB Output is correct
11 Correct 5 ms 1232 KB Output is correct
12 Correct 5 ms 1232 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2372 KB Output is correct
2 Correct 49 ms 1944 KB Output is correct
3 Correct 41 ms 3400 KB Output is correct
4 Correct 54 ms 4000 KB Output is correct
5 Correct 74 ms 4164 KB Output is correct
6 Correct 79 ms 4152 KB Output is correct
7 Correct 67 ms 4136 KB Output is correct
8 Correct 68 ms 4140 KB Output is correct
9 Correct 72 ms 4208 KB Output is correct
10 Correct 64 ms 4164 KB Output is correct
11 Correct 71 ms 4128 KB Output is correct
12 Correct 79 ms 4260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2156 KB Output is correct
2 Correct 62 ms 18760 KB Output is correct
3 Correct 60 ms 10960 KB Output is correct
4 Correct 159 ms 6892 KB Output is correct
5 Correct 350 ms 32448 KB Output is correct
6 Correct 580 ms 59632 KB Output is correct
7 Correct 63 ms 5312 KB Output is correct
8 Correct 279 ms 26980 KB Output is correct
9 Correct 163 ms 23112 KB Output is correct
10 Correct 194 ms 26952 KB Output is correct
11 Correct 173 ms 23160 KB Output is correct
12 Correct 226 ms 32200 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 11464 KB Output is correct
2 Correct 177 ms 13236 KB Output is correct
3 Correct 240 ms 29360 KB Output is correct
4 Correct 213 ms 11016 KB Output is correct
5 Correct 250 ms 24528 KB Output is correct
6 Correct 293 ms 30024 KB Output is correct
7 Correct 261 ms 24596 KB Output is correct
8 Correct 400 ms 40944 KB Output is correct
9 Correct 250 ms 33608 KB Output is correct
10 Correct 254 ms 40776 KB Output is correct
11 Correct 182 ms 26312 KB Output is correct
12 Correct 396 ms 61012 KB Output is correct