oj.uz

답안 #477368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477368 2021-10-01T19:41:52 Z ocarima Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 162 ms 11980 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 31
#define actplaca 1
#define aerosol 2
#define obtensuma 3

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

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;
    }
}

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 (s < e){
            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 && 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 4304 KB Output is correct
2 Correct 51 ms 3684 KB Output is correct
3 Correct 47 ms 5076 KB Output is correct
4 Correct 55 ms 6088 KB Output is correct
5 Correct 76 ms 6628 KB Output is correct
6 Correct 70 ms 6600 KB Output is correct
7 Correct 68 ms 6600 KB Output is correct
8 Correct 78 ms 6548 KB Output is correct
9 Correct 65 ms 6472 KB Output is correct
10 Correct 71 ms 6520 KB Output is correct
11 Correct 68 ms 6400 KB Output is correct
12 Correct 69 ms 6516 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 162 ms 11980 KB Output isn't correct
2 Halted 0 ms 0 KB -