oj.uz

답안 #493950

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493950 2021-12-13T13:12:05 Z alextodoran Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1277 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;
            if (K == 1) {
                continue;
            }
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 13 ms 332 KB Output is correct
5 Correct 16 ms 468 KB Output is correct
6 Correct 12 ms 464 KB Output is correct
7 Correct 15 ms 460 KB Output is correct
8 Correct 12 ms 472 KB Output is correct
9 Correct 15 ms 468 KB Output is correct
10 Correct 11 ms 460 KB Output is correct
11 Correct 10 ms 472 KB Output is correct
12 Correct 12 ms 472 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 4068 KB Output is correct
2 Correct 40 ms 4456 KB Output is correct
3 Correct 43 ms 6644 KB Output is correct
4 Correct 46 ms 7252 KB Output is correct
5 Correct 55 ms 7696 KB Output is correct
6 Correct 59 ms 7676 KB Output is correct
7 Correct 57 ms 7624 KB Output is correct
8 Correct 66 ms 7688 KB Output is correct
9 Correct 71 ms 7584 KB Output is correct
10 Correct 54 ms 7500 KB Output is correct
11 Correct 52 ms 7556 KB Output is correct
12 Correct 50 ms 7496 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 628 KB Output is correct
2 Correct 18 ms 2508 KB Output is correct
3 Correct 24 ms 2564 KB Output is correct
4 Correct 67 ms 1480 KB Output is correct
5 Correct 82 ms 4928 KB Output is correct
6 Correct 80 ms 4820 KB Output is correct
7 Correct 64 ms 5880 KB Output is correct
8 Correct 88 ms 6216 KB Output is correct
9 Correct 109 ms 6112 KB Output is correct
10 Correct 79 ms 6084 KB Output is correct
11 Correct 85 ms 6096 KB Output is correct
12 Correct 105 ms 6080 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 2668 KB Output is correct
2 Correct 260 ms 2824 KB Output is correct
3 Correct 482 ms 2664 KB Output is correct
4 Correct 334 ms 1760 KB Output is correct
5 Correct 425 ms 5052 KB Output is correct
6 Correct 547 ms 5072 KB Output is correct
7 Correct 406 ms 5112 KB Output is correct
8 Correct 796 ms 5068 KB Output is correct
9 Correct 698 ms 5056 KB Output is correct
10 Correct 898 ms 5184 KB Output is correct
11 Correct 523 ms 5056 KB Output is correct
12 Correct 1277 ms 5116 KB Output is correct