oj.uz

Submission #1026467

# Submission time Handle Problem Language Result Execution time Memory
1026467 2024-07-18T06:30:25 Z KienTran Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 257 ms 34736 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 1e5 + 5;
const int N = (1 << 10) + 5;
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};
const int base = 50;
const int K = 32;

int n, q, k, a[K][O], id[O], L[O], R[O], tree[O * 4];
long long sum[K][O];

void Del(int l){
    int block = l / base;

    int d = id[block];
    for (int i = 0; i < K; ++ i){
        int x = i + d >= K ? 0 : sum[i + d][block] - a[i + d][l];
        sum[i][block] = x;
    }
    return;
}

void Add(int l, int r){
    int block = l / base;

    a[0][l] = r;
    for (int i = 0; i < K; ++ i){
        if (i) a[i][l] = a[i - 1][l] / k;
        sum[i][block] += a[i][l];
    }
    return;
}

void Build(int id, int l, int r){
    if (l == r){
        tree[id] = a[0][r];
        return;
    }
    int mid = (l + r) / 2;
    Build(id << 1, l, mid);
    Build(id << 1 | 1, mid + 1, r);
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

void Update(int id, int l, int r, int u, int x){
    if (l > u || r < u) return;
    if (l == r){
        tree[id] = x;
        return;
    }
    int mid = (l + r) / 2;
    Update(id << 1, l, mid, u, x);
    Update(id << 1 | 1, mid + 1, r, u, x);
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

int Get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) return tree[id];
    int mid = (l + r) / 2;
    return Get(id << 1, l, mid, u, v) + Get(id << 1 | 1, mid + 1, r, u, v);
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q >> k;
    for (int i = 0; i < n; ++ i){
        cin >> a[0][i];

        int block = i / base;
        R[block] = i;

        for (int j = 0; j < K; ++ j){
            if (j) a[j][i] = a[j - 1][i] / k;
            sum[j][block] += a[j][i];
        }
    }


    for (int i = n - 1; i >= 0; -- i){
        L[i / base] = i;
    }

    if (k == 1){
        n -= 1;
        Build(1, 0, n);
        for (int i = 1; i <= q; ++ i){
            int t, l, r; cin >> t >> l >> r;
            if (t == 1){
                l -= 1;
                Update(1, 0, n, l, r);
            }

            if (t == 3){
                l -= 1; r -= 1;
                cout << Get(1, 0, n, l, r) << "\n";
            }
        }

        return 0;
    }

    for (int _ = 1; _ <= q; ++ _){
        int t, l, r; cin >> t >> l >> r;
        l -= 1; r -= 1;

        if (t == 1){
            r += 1;
            Del(l);
            Add(l, r);

            int block = l / base, d = id[l / base];
            for (int i = L[block]; i <= R[block]; ++ i){
                if (i != l){
                    for (int j = 0; j < K; ++ j){
                        int x = j + d >= K ? 0 : a[j + d][i];
                        a[j][i] = x;
                    }
                }
            }

            id[block] = 0;
        }

        if (t == 2){
            for (int i = (l / base) + 1; i < (r / base); ++ i) id[i] = min(id[i] + 1, K - 1);

            for (int i = l; i <= min(R[l / base], r); ++ i){
                for (int j = id[l / base]; j < K; ++ j){
                    int x = j + 1 >= K ? 0 : a[j + 1][i];
                    sum[j][l / base] -= a[j][i];
                    sum[j][l / base] += x;
                    a[j][i] = x;
                }
            }

            if ((int)l / base != (int)r / base){
                for (int i = L[r / base]; i <= r; ++ i){
                    for (int j = id[r / base]; j < K; ++ j){
                        int x = j + 1 >= K ? 0 : a[j + 1][i];
                        sum[j][r / base] -= a[j][i];
                        sum[j][r / base] += x;
                        a[j][i] = x;
                    }
                }
            }
        }

        if (t == 3){
            long long res = 0;

            for (int i = l / base; i <= r / base; ++ i){
                res += sum[id[i]][i];
            }

            for (int i = L[l / base]; i < l; ++ i) res -= a[id[l / base]][i];
            for (int i = r + 1; i <= R[r / base]; ++ i) res -= a[id[r / base]][i];

            cout << res << "\n";
        }
    }

}
/**
4 9 2
1 1 1 1
2 2 3
3 2 3
2 2 3
3 2 3
2 2 3
3 2 3
1 2 11
3 1 3
3 2 3
**/

Compilation message

sterilizing.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 3 ms 29392 KB Output is correct
4 Correct 7 ms 29420 KB Output is correct
5 Correct 6 ms 29272 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 6 ms 29452 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 7 ms 29276 KB Output is correct
11 Correct 6 ms 29276 KB Output is correct
12 Correct 7 ms 29444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 32084 KB Output is correct
2 Correct 37 ms 33628 KB Output is correct
3 Correct 38 ms 33620 KB Output is correct
4 Correct 44 ms 34388 KB Output is correct
5 Correct 50 ms 34736 KB Output is correct
6 Correct 51 ms 34640 KB Output is correct
7 Correct 51 ms 34644 KB Output is correct
8 Correct 63 ms 34628 KB Output is correct
9 Correct 49 ms 34640 KB Output is correct
10 Correct 47 ms 34648 KB Output is correct
11 Correct 48 ms 34672 KB Output is correct
12 Correct 51 ms 34644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 29276 KB Output is correct
2 Correct 25 ms 29528 KB Output is correct
3 Correct 33 ms 29528 KB Output is correct
4 Correct 98 ms 29524 KB Output is correct
5 Correct 130 ms 29784 KB Output is correct
6 Correct 130 ms 29856 KB Output is correct
7 Correct 54 ms 31980 KB Output is correct
8 Correct 147 ms 31568 KB Output is correct
9 Correct 207 ms 31060 KB Output is correct
10 Correct 214 ms 31056 KB Output is correct
11 Correct 233 ms 31316 KB Output is correct
12 Correct 206 ms 31056 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 29776 KB Output is correct
2 Correct 92 ms 29780 KB Output is correct
3 Correct 60 ms 29604 KB Output is correct
4 Correct 105 ms 29588 KB Output is correct
5 Correct 137 ms 30052 KB Output is correct
6 Correct 130 ms 30108 KB Output is correct
7 Correct 136 ms 30036 KB Output is correct
8 Correct 131 ms 30032 KB Output is correct
9 Correct 257 ms 30148 KB Output is correct
10 Correct 236 ms 30036 KB Output is correct
11 Correct 230 ms 30028 KB Output is correct
12 Correct 220 ms 30036 KB Output is correct