oj.uz

Submission #1026452

# Submission time Handle Problem Language Result Execution time Memory
1026452 2024-07-18T06:15:18 Z KienTran Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 111 ms 15068 KB 
#include <bits/stdc++.h>

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];
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;
}

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;
    }

    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;
                }
            }
            //cout << a[0][l] << "ye" << endl;


            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;
                    }
                }
            }
            //cout << a[0][r] << "ye" << endl;
        }

        //if ()
        //for (int j = 0; j < n; ++ j){
            //cout << a[id[j / base]][j] << " ";
        //}

        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:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 14316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12888 KB Output is correct
2 Correct 20 ms 13912 KB Output is correct
3 Correct 28 ms 13660 KB Output is correct
4 Correct 84 ms 13560 KB Output is correct
5 Correct 109 ms 15068 KB Output is correct
6 Correct 111 ms 14940 KB Output is correct
7 Incorrect 108 ms 14940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 14164 KB Output isn't correct
2 Halted 0 ms 0 KB -