oj.uz

Submission #202986

# Submission time Handle Problem Language Result Execution time Memory
202986 2020-02-18T21:16:21 Z tri Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1342 ms 161456 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;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 156920 KB Output is correct
2 Correct 94 ms 156920 KB Output is correct
3 Correct 90 ms 156920 KB Output is correct
4 Correct 115 ms 157048 KB Output is correct
5 Correct 110 ms 157048 KB Output is correct
6 Correct 112 ms 157052 KB Output is correct
7 Correct 109 ms 157048 KB Output is correct
8 Correct 113 ms 157048 KB Output is correct
9 Correct 110 ms 157048 KB Output is correct
10 Correct 109 ms 157048 KB Output is correct
11 Correct 111 ms 157048 KB Output is correct
12 Correct 109 ms 157048 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 158200 KB Output is correct
2 Correct 724 ms 159864 KB Output is correct
3 Correct 665 ms 160376 KB Output is correct
4 Correct 848 ms 161144 KB Output is correct
5 Correct 998 ms 161424 KB Output is correct
6 Correct 1022 ms 161456 KB Output is correct
7 Correct 1024 ms 161400 KB Output is correct
8 Correct 1010 ms 161404 KB Output is correct
9 Correct 902 ms 161144 KB Output is correct
10 Correct 911 ms 161400 KB Output is correct
11 Correct 909 ms 161400 KB Output is correct
12 Correct 907 ms 161400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 157048 KB Output is correct
2 Correct 271 ms 157816 KB Output is correct
3 Correct 361 ms 157688 KB Output is correct
4 Correct 976 ms 157432 KB Output is correct
5 Correct 1266 ms 158712 KB Output is correct
6 Correct 1283 ms 158712 KB Output is correct
7 Correct 942 ms 158780 KB Output is correct
8 Correct 1298 ms 160036 KB Output is correct
9 Correct 1157 ms 159992 KB Output is correct
10 Correct 1161 ms 159880 KB Output is correct
11 Correct 1189 ms 160044 KB Output is correct
12 Correct 1187 ms 159992 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 157956 KB Output is correct
2 Correct 988 ms 158328 KB Output is correct
3 Correct 629 ms 158072 KB Output is correct
4 Correct 1022 ms 157952 KB Output is correct
5 Correct 1332 ms 158968 KB Output is correct
6 Correct 1342 ms 158844 KB Output is correct
7 Correct 1340 ms 159224 KB Output is correct
8 Correct 1321 ms 159212 KB Output is correct
9 Correct 1207 ms 159096 KB Output is correct
10 Correct 1222 ms 158968 KB Output is correct
11 Correct 1202 ms 158840 KB Output is correct
12 Correct 1221 ms 159000 KB Output is correct