oj.uz

Submission #1026453

# Submission time Handle Problem Language Result Execution time Memory
1026453 2024-07-18T06:16:24 Z KienTran Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 255 ms 31420 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];
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:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Incorrect 4 ms 27228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 27412 KB Output is correct
2 Correct 22 ms 27740 KB Output is correct
3 Correct 29 ms 27736 KB Output is correct
4 Correct 85 ms 27484 KB Output is correct
5 Correct 117 ms 28764 KB Output is correct
6 Correct 114 ms 28760 KB Output is correct
7 Incorrect 118 ms 28760 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 28012 KB Output is correct
2 Correct 82 ms 29776 KB Output is correct
3 Correct 52 ms 29016 KB Output is correct
4 Correct 85 ms 29520 KB Output is correct
5 Correct 122 ms 31312 KB Output is correct
6 Correct 133 ms 31332 KB Output is correct
7 Correct 121 ms 31420 KB Output is correct
8 Correct 120 ms 31368 KB Output is correct
9 Correct 236 ms 31316 KB Output is correct
10 Correct 218 ms 31312 KB Output is correct
11 Correct 198 ms 31316 KB Output is correct
12 Correct 255 ms 31312 KB Output is correct