oj.uz

Submission #1026422

# Submission time Handle Problem Language Result Execution time Memory
1026422 2024-07-18T05:39:28 Z KienTran Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 359 ms 15692 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 = 1e18;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};
const int base = 50;
const int K = 31;

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[l / base] = 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){
                int x = a[id[i / base]][i] / k;
                Del(i); Add(i, x);
            }

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

            id[l / base] = 0;

            if (l / base != r / base){
                for (int i = L[r / base]; i <= r; ++ i){
                    int x = a[id[i / base]][i] / k;
                    Del(i); Add(i, x);
                }

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

                id[r / base] = 0;
            }
        }

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

}
/**
1
3
3 1 2
**/

Compilation message

sterilizing.cpp:8:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | const int inf = 1e18;
      |                 ^~~~
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 6 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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