oj.uz

답안 #1026443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026443 2024-07-18T06:04:28 Z KienTran Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 795 ms 28596 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 = 2;
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){
                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 ((int)l / base != (int)r / base){
                for (int i = L[r / base]; i <= r; ++ i){
                    int x = a[id[i / base]][i] / k;
                    Del(i); Add(i, x);
                }

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

}
/**
4 9 2
11 11 11 11
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 382 ms 20136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 13656 KB Output is correct
2 Correct 74 ms 19292 KB Output is correct
3 Correct 99 ms 19536 KB Output is correct
4 Correct 205 ms 17424 KB Output is correct
5 Correct 747 ms 28456 KB Output is correct
6 Correct 795 ms 28496 KB Output is correct
7 Incorrect 699 ms 28596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 277 ms 20448 KB Output isn't correct
2 Halted 0 ms 0 KB -