oj.uz

답안 #581979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581979 2022-06-23T09:05:25 Z Jarif_Rahman Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 ms 144376 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int K, C;

struct segtree{
    struct node{
        int divisions;
        deque<ll> d;
        node(){
            divisions = 0;
            d.assign(C, 0);
        }
        node(ll x){
            divisions = 0;
            d.assign(C, 0);
            for(int i = 0; i < C; i++){
                d[i] = x%K;
                x/=K;
            }
            reverse(d.begin(), d.end());
        }
        node operator+(node &a){
            node rt;
            for(int i = 0; i < C; i++) rt.d[i] = d[i]+a.d[i];
            return rt;
        }
        void pushdown_from(node &p){
            int x = p.divisions;
            if(x >= C) d.assign(C, 0);
            else{
                while(x--) d.pop_back(), d.push_front(0);
            } 
        }
    };

    int k;
    vector<node> v;

    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.assign(k, node());
    }

    void update(int in, int nd, int a, int b, ll x){
        if(a == b){
            v[nd] = node(x);
            return;
        }
        int md = (a+b)/2;

        v[2*nd].pushdown_from(v[nd]);
        v[2*nd+1].pushdown_from(v[nd]);
        v[nd].divisions = 0;

        if(in <= md) update(in, 2*nd, a, md, x);
        else update(in, 2*nd+1, md+1, b, x);

        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void update(int in, ll x){
        update(in, 1, 0, k/2-1, x);
    }

    void spray(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            v[nd].d.pop_back();
            v[nd].d.push_front(0);
            v[nd].divisions++;
            return;
        }

        int md = (a+b)/2;

        v[2*nd].pushdown_from(v[nd]);
        v[2*nd+1].pushdown_from(v[nd]);
        v[nd].divisions = 0;

        spray(l, r, 2*nd, a, md);
        spray(l, r, 2*nd+1, md+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
    }
    void spray(int l, int r){
        spray(l, r, 1, 0, k/2-1);
    }

    ll sum(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return 0;
        if(a >= l && b <= r){
            ll p = 1, s = 0;
            for(int i = C-1; i >= 0; i--) s+=v[nd].d[i]*p, p*=K;
            return s;
        }

        int md = (a+b)/2;

        v[2*nd].pushdown_from(v[nd]);
        v[2*nd+1].pushdown_from(v[nd]);
        v[nd].divisions = 0;

        ll rt = sum(l, r, 2*nd, a, md) + sum(l, r, 2*nd+1, md+1, b);
        v[nd] = v[2*nd]+v[2*nd+1];
        return rt;
    }
    ll sum(int l, int r){
        return sum(l, r, 1, 0, k/2-1);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q >> K;

    ll p = 1; C = 0;
    while(p < ll(1e9)) p*=K, C++;

    segtree seg(n);

    for(int i = 0; i < n; i++){
        ll x; cin >> x;
        seg.update(i, x);
    }

    while(q--){
        int tt; cin >> tt;
        if(tt == 1){
            int in; ll x; cin >> in >> x; in--;
            seg.update(in, x);
        }
        if(tt == 2){
            int l, r; cin >> l >> r; l--, r--;
            seg.spray(l, r);
        }
        if(tt == 3){
            int l, r; cin >> l >> r; l--, r--;
            cout << seg.sum(l, r) << "\n";
        }
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5067 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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