Submission #1128477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128477		ByeWorld	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	408 ms	69344 KiB

sterilizing

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 32;
const ld EPS = 1e-12;

int n, q, k, a[MAXN];

struct node {
    int val[LOG];
} NOL;
node make(int x){
    node ret = NOL;
    if(k==1){
        ret.val[0] = x;
        return ret;
    }
    for(int i=0; i<LOG; i++){
        ret.val[i] = x % k;
        x /= k;
    }
    return ret;
}
struct seg {
    node st[4*MAXN]; int laz[4*MAXN];
    void op(int id, int num){
        if(k==1){
            return;
        }
        
        laz[id] += num;
        for(int i=0; i+num<LOG; i++)
            st[id].val[i] = st[id].val[i+num];
        for(int i=LOG-1; i>=max(0ll,LOG-num); i--)
            st[id].val[i] = 0;
    }
    void bnc(int id, int l, int r){
        if(laz[id] == 0) return;
        op(lf, laz[id]); op(rg, laz[id]);
        laz[id] = 0;
    }
    node mrg(node a, node b){
        node ret = NOL;
        for(int i=0; i<LOG; i++) 
            ret.val[i] = a.val[i]+b.val[i];
        return ret;
    }
    void bd(int id, int l, int r){
        if(l==r){ st[id] = make(a[l]); return; }
        bd(lf,l,md); bd(rg,md+1,r);
        st[id] = mrg(st[lf], st[rg]);
    }
    node add(int id,int l, int r, int x, int val){
        if(x==l && l==r){
            laz[id] = 0; 
            return st[id] = make(val);
        }
        if(r<x || x<l) return st[id];
        bnc(id, l, r);
        return st[id] = mrg(add(lf,l,md,x,val), add(rg,md+1,r,x,val));
    }
    node upd(int id,int l,int r, int x, int y){
        if(x<=l && r<=y){
            op(id, 1);
            return st[id];
        }
        if(r<x || y<l) return st[id];
        bnc(id,l,r);
        return st[id] = mrg(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
    }
    node que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return NOL;
        bnc(id,l,r);
        return mrg(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
    }
} A;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=0; i<LOG; i++) NOL.val[i] = 0;

    cin >> n >> q >> k;
    for(int i=1; i<=n; i++) cin >> a[i];

    A.bd(1,1,n);
    while(q--){
        int ty, l, r; cin>>ty>>l>>r;
        if(ty==1){
            A.add(1,1,n,l,r);
        } else if(ty==2){
            A.upd(1,1,n,l,r);
        } else {
            node ret = A.que(1,1,n,l,r);
            if(k==1){
                cout << ret.val[0] << '\n';
                continue;
            }

            int ans = 0;
            for(int i=LOG-1; i>=0; i--){
                ans *= k; ans += ret.val[i];
            }
            cout << ans << '\n';
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75