oj.uz

답안 #202983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202983 2020-02-18T21:03:45 Z tri Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 1310 ms 159224 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const int MAXN = 1e5 + 10;
const int MAXP = 50;

struct sums {
    ll v[MAXP];

    sums() {
        memset(v, 0, sizeof(v));
    }

    sums const operator+(sums o) {
        sums ret;
        for (int i = 0; i < MAXP; i++) {
            ret.v[i] = v[i] + o.v[i];
        }
        return ret;
    }

    void shift(int x) {
        for (int i = 0; i < MAXP; i++) {
            if (i + x < MAXP) {
                v[i] = v[i + x];
            } else {
                v[i] = 0;
            }
        }
    }
};

int N, Q, K;

sums convert(int v) {
    sums ret;
    ret.v[0] = v;
    for (int p = 1; p < MAXP; p++) {
        ret.v[p] = ret.v[p - 1] / K;
    }
    return ret;
}

struct LSegTr {
    sums tr[4 * MAXN];
    int lz[4 * MAXN];

    void b(int i, int l, int r, vi &init) {
        lz[i] = 0;
        if (l == r) {
            tr[i] = convert(init[l]);
            return;
        }
        int mid = (l + r) / 2;
        b(i * 2, l, mid, init);
        b(i * 2 + 1, mid + 1, r, init);
        tr[i] = tr[i * 2] + tr[i * 2 + 1];
    }

    void push(int i, int l, int r) {
        tr[i].shift(lz[i]);
        if (l != r) {
            lz[i * 2] += lz[i];
            lz[i * 2 + 1] += lz[i];
        }
        lz[i] = 0;
    }

    sums q(int i, int l, int r, int s, int e) {
        if (e < l || r < s) {
            return sums();
        }
        push(i, l, r);
        if (s <= l && r <= e) {
            return tr[i];
        }
        int mid = (l + r) / 2;
        return q(i * 2, l, mid, s, e) + q(i * 2 + 1, mid + 1, r, s, e);
    }

    void uShift(int i, int l, int r, int s, int e, int d) {
//        ps(i, l, r, d);
        push(i, l, r); // pushed early to use in recalculation of parent
        if (e < l || r < s) {
            return;
        }
        if (s <= l && r <= e) {
            lz[i] += d;
            push(i, l, r);
            return;
        }
        int mid = (l + r) / 2;
        uShift(i * 2, l, mid, s, e, d);
        uShift(i * 2 + 1, mid + 1, r, s, e, d);
        tr[i] = tr[i * 2] + tr[i * 2 + 1];
    }

    void u(int i, int l, int r, int x, int v) {
        push(i, l, r);
        if (l == r) {
            tr[i] = convert(v);
            return;
        }
        int mid = (l + r) / 2;
        push(i * 2, l, mid);
        push(i * 2 + 1, mid + 1, r);

        if (x <= mid) {
            u(i * 2, l, mid, x, v);
        } else {
            u(i * 2 + 1, mid + 1, r, x, v);
        }
        
        tr[i] = tr[i * 2] + tr[i * 2 + 1];
    }
} lSegTr;

int main() {
    cin >> N >> Q >> K;
    vi init(N);
    for (int i = 0; i < N; i++) {
        cin >> init[i];
    }
    lSegTr.b(1, 0, N - 1, init);

    for (int i = 0; i < Q; i++) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            lSegTr.u(1, 0, N - 1, l - 1, r);
        } else if (t == 2) {
            lSegTr.uShift(1, 0, N - 1, l - 1, r - 1, 1);
        } else {
            assert(t == 3);
            sums ansSum = lSegTr.q(1, 0, N - 1, l - 1, r - 1);
            ll ans = ansSum.v[0];
            cout << ans << endl;
        }
    }
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 156920 KB Output is correct
2 Incorrect 95 ms 157048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 157268 KB Output is correct
2 Correct 264 ms 157816 KB Output is correct
3 Correct 357 ms 157816 KB Output is correct
4 Correct 978 ms 157688 KB Output is correct
5 Correct 1252 ms 158840 KB Output is correct
6 Correct 1268 ms 158712 KB Output is correct
7 Incorrect 1264 ms 158712 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 876 ms 158336 KB Output is correct
2 Correct 982 ms 158096 KB Output is correct
3 Correct 637 ms 158060 KB Output is correct
4 Correct 1002 ms 157820 KB Output is correct
5 Correct 1306 ms 159224 KB Output is correct
6 Correct 1303 ms 159096 KB Output is correct
7 Correct 1298 ms 159028 KB Output is correct
8 Correct 1310 ms 158968 KB Output is correct
9 Correct 1203 ms 158968 KB Output is correct
10 Correct 1217 ms 159096 KB Output is correct
11 Correct 1184 ms 158968 KB Output is correct
12 Correct 1182 ms 158968 KB Output is correct