oj.uz

답안 #483652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483652 2021-10-31T12:59:50 Z Mahfel Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 2489 ms 37996 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 2e5 + 20 , LOG = 35;
#define lt(x) 2*x+1
#define rt(x) 2*x+2
int n,q,k;
int a[MXN];

struct seg_tree {
    int size;
    vector<ll> v[LOG] , d;
    seg_tree() {
        size = 0;
    }
    void init() {
        size = 1;
        while(size < n) size <<= 1;
        for(int i = 0 ; i < LOG ; i++) v[i].assign(2*size , 0);
        d.assign(2*size , 0);
    }
    void build(int x , int lx , int rx) {
        if(rx-lx == 1) {
            if(lx < n) {
                v[0][x] = a[lx];
                for(int i = 1 ; i < LOG ; i++) {
                    v[i][x] = v[i-1][x]/k;
                }
            }
            return;
        }
        int m = (lx+rx)/2;
        build(lt(x) , lx , m); build(rt(x) , m , rx);
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        }
    }
    void build() {
        build(0 , 0 , size);
    }

    void shift(int x , int lx , int rx) {
        if(rx-lx == 1) return;
        d[lt(x)] += d[x];
        d[rt(x)] += d[x];
    }
    void update(int x , int lx , int rx) {
        for(int i = 0 ; i < LOG ; i++) {
            v[i][x] = (i+d[x] < LOG ? v[i+d[x]][x] : 0);
        }
        d[x] = 0;
    }

    void set(int x , int lx , int rx , int i , ll k) {
        if(rx-lx == 1) {
            v[0][x] = k;
            for(int i = 1 ; i < LOG ; i++) {
                v[i][x] = v[i-1][x]/k;
            }
            d[x] = 0;
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        if(i < m) {
            set(lt(x) , lx , m , i , k);
            shift(rt(x) , m , rx); update(rt(x) , m , rx);
        } else {
            set(rt(x) , m , rx , i , k);
            shift(lt(x) , lx , m); update(lt(x) , lx , m);
        }
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void set(int i , ll k) {
        set(0 , 0 , size , i , k);
    }

    void divide(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            d[x]++;
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        divide(lt(x) , lx , m , l , r);
        divide(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
    }
    void divide(int l , int r) {
        divide(0 , 0 , size , l , r);
    }

    ll sum(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return d[x] >= LOG ? 0 : v[d[x]][x];
        }
        if(lx >= r || rx <= l) {
            shift(x , lx , rx);
            update(x , lx , rx);
            return 0;
        }
        shift(x , lx , rx);
        int m = (lx+rx)/2;
        ll a = sum(lt(x) , lx , m , l , r) , b = sum(rt(x) , m , rx , l , r);
        d[x] = 0;
        for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
        return a+b;
    }
    ll sum(int l , int r) {
        return sum(0 , 0 , size , l , r);
    }
} seg;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> q >> k;
    for(int i = 0 ; i < n ; i++) {
        cin >> a[i];
    }
    seg.init(); seg.build();

    while(q--) {

        int type,x,y; cin >> type >> x >> y;
        if(type == 1) {
            seg.set(x-1 , y);
        }
        if(type == 2) {
            seg.divide(x-1 , y);
        }
        if(type == 3) {
            cout << seg.sum(x-1 , y) << "\n";
        }

    }

}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 10076 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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