Submission #567976

#	Time	Username	Problem	Language	Result	Execution time	Memory
567976		urosk	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	858 ms	81044 KiB

sterilizing

// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

#define maxn 200005
#define lg 35
ll n,q,k;
ll a[maxn];
ll lazy[4*maxn];
vector<ll> t[4*maxn];
vector<ll> mrg(vector<ll> a,vector<ll> b){
    vector<ll> c(lg);
    for(ll i = 0;i<lg;i++) c[i] = a[i] + b[i];
    return c;
}
vector<ll> f(ll x){
    vector<ll> c(lg);
    ll y = x;
    for(ll i = 0;i<lg;i++){
        c[i] = y;
        y/=k;
    }
    return c;
}
void push(ll v,ll tl,ll tr){
    ll x = lazy[v];
    while(lazy[v]>0&&t[v][0]>0){
        for(ll i = 0;i<lg-1;i++) t[v][i] = t[v][i+1];
        t[v][lg-1] = 0;
        lazy[v]--;
    }
    lazy[v] = x;
    if(tl<tr){
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
    }
    lazy[v] = 0;
}
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v] = f(a[tl]);
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid);
    init(2*v+1,mid+1,tr);
    t[v] = mrg(t[2*v],t[2*v+1]);
}
void upd(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r) return;
    if(tl==l&&tr==r){
        lazy[v]++;
        push(v,tl,tr);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(2*v,tl,mid,l,min(mid,r));
    upd(2*v+1,mid+1,tr,max(mid+1,l),r);
    push(2*v,tl,mid);
    push(2*v+1,mid+1,tr);
    t[v] = mrg(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r) return 0;
    if(tl==l&&tr==r) return t[v][0];
    ll mid = (tl+tr)/2;
    return get(2*v,tl,mid,l,min(mid,r)) + get(2*v+1,mid+1,tr,max(mid+1,l),r);
}
void check(ll v,ll tl,ll tr){
    cerr<<"range: "<<tl<< " "<<tr<<endl;
    for(ll x : t[v]) cerr<<x<< " ";
    cerr<<endl;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    check(2*v,tl,mid);
    check(2*v+1,mid+1,tr);
}
void upd2(ll v,ll tl,ll tr,ll i,ll x){
    push(v,tl,tr);
    if(tl==tr){
        t[v] = f(x);
        return;
    }
    ll mid = (tl+tr)/2;
    if(i<=mid) upd2(2*v,tl,mid,i,x);
    else upd2(2*v+1,mid+1,tr,i,x);
    push(2*v,tl,mid);
    push(2*v+1,mid+1,tr);
    t[v] = mrg(t[2*v],t[2*v+1]);
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> q >> k;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    init(1,1,n);
    while(q--){
        ll tip; cin >> tip;
        if(tip==1){
            ll i,x;
            cin >> i >> x;
            upd2(1,1,n,i,x);
        }else if(tip==2){
            ll l,r; cin >> l >> r;
            if(k==1) continue;
            upd(1,1,n,l,r);
        }else{
            ll l,r; cin >> l >> r;
            cout<<get(1,1,n,l,r)<<endl;
        }
    }
	return 0;
}

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