oj.uz

답안 #582037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582037 2022-06-23T09:52:20 Z Jarif_Rahman Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 2593 ms 285004 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 BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, ll x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};

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;
            divisions+=x;
            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;

    if(K == 1){
        BIT bit(n);
        for(int i = 0; i < n; i++){
            ll x; cin >> x;
            bit.add(i, x);
        }
        while(q--){
            int tt; cin >> tt;
            if(tt == 1){
                int in; ll x; cin >> in >> x; in--;
                bit.add(in, x-bit.sum(in, in));
            }
            if(tt == 2){
                int l, r; cin >> l >> r; l--, r--;
                //do nothing
            }
            if(tt == 3){
                int l, r; cin >> l >> r; l--, r--;
                cout << bit.sum(l, r) << "\n";
            }
        }
        exit(0);
    }

    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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 5020 KB Output is correct
4 Correct 22 ms 4564 KB Output is correct
5 Correct 30 ms 9076 KB Output is correct
6 Correct 26 ms 9040 KB Output is correct
7 Correct 28 ms 9076 KB Output is correct
8 Correct 28 ms 8988 KB Output is correct
9 Correct 42 ms 9084 KB Output is correct
10 Correct 33 ms 9036 KB Output is correct
11 Correct 29 ms 9080 KB Output is correct
12 Correct 28 ms 9032 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 3068 KB Output is correct
2 Correct 31 ms 2600 KB Output is correct
3 Correct 30 ms 2840 KB Output is correct
4 Correct 44 ms 3504 KB Output is correct
5 Correct 38 ms 3944 KB Output is correct
6 Correct 39 ms 3916 KB Output is correct
7 Correct 42 ms 3984 KB Output is correct
8 Correct 43 ms 4032 KB Output is correct
9 Correct 40 ms 3800 KB Output is correct
10 Correct 38 ms 3852 KB Output is correct
11 Correct 42 ms 3916 KB Output is correct
12 Correct 44 ms 3900 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 18476 KB Output is correct
2 Correct 449 ms 136096 KB Output is correct
3 Correct 591 ms 136344 KB Output is correct
4 Correct 1100 ms 71676 KB Output is correct
5 Correct 2043 ms 283596 KB Output is correct
6 Correct 2462 ms 283664 KB Output is correct
7 Correct 42 ms 2636 KB Output is correct
8 Correct 2011 ms 283788 KB Output is correct
9 Correct 1393 ms 283516 KB Output is correct
10 Correct 1293 ms 283516 KB Output is correct
11 Correct 1303 ms 283500 KB Output is correct
12 Correct 1617 ms 283624 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1166 ms 144372 KB Output is correct
2 Correct 1292 ms 145328 KB Output is correct
3 Correct 1129 ms 137240 KB Output is correct
4 Correct 1261 ms 80084 KB Output is correct
5 Correct 2060 ms 285004 KB Output is correct
6 Correct 2045 ms 284876 KB Output is correct
7 Correct 2057 ms 284908 KB Output is correct
8 Correct 2593 ms 284956 KB Output is correct
9 Correct 1907 ms 284756 KB Output is correct
10 Correct 2021 ms 284876 KB Output is correct
11 Correct 1680 ms 284728 KB Output is correct
12 Correct 2084 ms 284728 KB Output is correct