Submission #202985

# Submission time Handle Problem Language Result Execution time Memory
202985 2020-02-18T21:15:02 Z tri Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
5000 ms 159240 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 = true;

    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;

int N, Q, K;

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) {
        if (K == 1) return;
        for (int i = 0; i < MAXP; i++) {
            if (i + x < MAXP) {
                v[i] = v[i + x];
            } else {
                v[i] = 0;
            }
        }
    }
};

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 a[MAXN];

void u(int x, int v) {
    a[x] = v;
}

void uShift(int l, int r) {
    for (int i = l; i <= r; i++) {
        a[i] /= K;
    }
}

ll sum(int l, int r) {
    ll s = 0;
    for (int i = l; i <= r; i++) {
        s += a[i];
    }
    return s;
}

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

    for (int i = 0; i < N; i++) {
        a[i] = init[i];
    }

    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);
            u(l - 1, r);
        } else if (t == 2) {
            lSegTr.uShift(1, 0, N - 1, l - 1, r - 1, 1);
            uShift(l - 1, r - 1);
        } else {
            assert(t == 3);
            sums ansSum = lSegTr.q(1, 0, N - 1, l - 1, r - 1);
            ll ans = ansSum.v[0];
            ll ans2 = sum(l - 1, r - 1);
            assert(ans == ans2);
            cout << ans << endl;
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 99 ms 156920 KB Output is correct
2 Correct 92 ms 157048 KB Output is correct
3 Correct 92 ms 157048 KB Output is correct
4 Correct 109 ms 157048 KB Output is correct
5 Correct 116 ms 157048 KB Output is correct
6 Correct 115 ms 157048 KB Output is correct
7 Correct 117 ms 157216 KB Output is correct
8 Correct 115 ms 157048 KB Output is correct
9 Correct 115 ms 157048 KB Output is correct
10 Correct 115 ms 157052 KB Output is correct
11 Correct 120 ms 157204 KB Output is correct
12 Correct 114 ms 157068 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 158584 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 535 ms 157432 KB Output is correct
2 Correct 622 ms 157816 KB Output is correct
3 Correct 928 ms 157944 KB Output is correct
4 Correct 2236 ms 157512 KB Output is correct
5 Execution timed out 5081 ms 159240 KB Time limit exceeded
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2701 ms 158376 KB Output is correct
2 Correct 3119 ms 158200 KB Output is correct
3 Correct 1771 ms 158200 KB Output is correct
4 Correct 2605 ms 157944 KB Output is correct
5 Execution timed out 5094 ms 159224 KB Time limit exceeded
6 Halted 0 ms 0 KB -