Submission #477537

#	Time	Username	Problem	Language	Result	Execution time	Memory
477537		ocarima	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	580 ms	61012 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75