oj.uz

Submission #493948

# Submission time Handle Problem Language Result Execution time Memory
493948 2021-12-13T13:11:04 Z alextodoran Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7696 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int Q_MAX = 100000;

int N, Q, K;

int C[N_MAX + 2];

struct SGTNode {
    int first;
    ll sum;
};

SGTNode operator + (const SGTNode &u, const SGTNode &v) {
    return SGTNode{(u.first != -1 ? u.first : v.first), u.sum + v.sum};
}

SGTNode SGT[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    if (l == r) {
        SGT[node].first = (C[l] > 0 ? l : -1);
        SGT[node].sum = C[l];
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void build () {
    build(1, 1, N);
}

void update (int node, int l, int r, int upos) {
    if (l == r) {
        SGT[node].first = (C[l] > 0 ? l : -1);
        SGT[node].sum = C[l];
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (upos <= mid) {
        update(lSon, l, mid, upos);
    } else {
        update(rSon, mid + 1, r, upos);
    }

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int upos) {
    update(1, 1, N, upos);
}

SGTNode query (int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return SGT[node];
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (ql <= mid && mid + 1 <= qr) {
        return query(lSon, l, mid, ql, qr) + query(rSon, mid + 1, r, ql, qr);
    } else if (ql <= mid) {
        return query(lSon, l, mid, ql, qr);
    } else {
        return query(rSon, mid + 1, r, ql, qr);
    }
}
SGTNode query (int ql, int qr) {
    return query(1, 1, N, ql, qr);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> Q >> K;
    for (int i = 1; i <= N; i++) {
        cin >> C[i];
    }
    build();
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int upos, uval;
            cin >> upos >> uval;
            C[upos] = uval;
            update(upos);
        } else if (type == 2) {
            int l, r;
            cin >> l >> r;
            while (l <= r) {
                int upos = query(l, r).first;
                if (upos != -1) {
                    C[upos] /= K;
                    update(upos);
                    l = upos + 1;
                } else {
                    break;
                }
            }
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(l, r).sum << "\n";
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 11 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 13 ms 460 KB Output is correct
5 Correct 13 ms 540 KB Output is correct
6 Correct 9 ms 460 KB Output is correct
7 Correct 12 ms 544 KB Output is correct
8 Correct 13 ms 592 KB Output is correct
9 Correct 16 ms 544 KB Output is correct
10 Correct 11 ms 464 KB Output is correct
11 Correct 10 ms 464 KB Output is correct
12 Correct 11 ms 540 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 3308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 976 KB Output is correct
2 Correct 20 ms 2804 KB Output is correct
3 Correct 24 ms 2944 KB Output is correct
4 Correct 54 ms 2632 KB Output is correct
5 Correct 80 ms 6252 KB Output is correct
6 Correct 79 ms 6204 KB Output is correct
7 Execution timed out 5079 ms 5300 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 4216 KB Output is correct
2 Correct 260 ms 4468 KB Output is correct
3 Correct 494 ms 3812 KB Output is correct
4 Correct 306 ms 3400 KB Output is correct
5 Correct 434 ms 7472 KB Output is correct
6 Correct 628 ms 7552 KB Output is correct
7 Correct 478 ms 7572 KB Output is correct
8 Correct 776 ms 7696 KB Output is correct
9 Correct 643 ms 7360 KB Output is correct
10 Correct 805 ms 7624 KB Output is correct
11 Correct 478 ms 7352 KB Output is correct
12 Correct 1158 ms 7520 KB Output is correct