Submission #521370

#	Time	Username	Problem	Language	Result	Execution time	Memory
521370		perchuts	Sterilizing Spray (JOI15_sterilizing)	C++17	20 / 100	198 ms	30476 KiB

sterilizing

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
pair<ii,vector<ll>>lazy[4*maxn];
int n,q;
ll k;
ll v[maxn],seg[4*maxn];

void build(int i,int l,int r){
    if(l==r){
        seg[i] = v[l];
        ll tmp = v[l];
        while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
        lazy[i].first={-1,0};
        return;
    }
    int md = (l+r)/2;
    build(2*i,l,md);
    build(2*i+1,md+1,r);
    seg[i] = seg[2*i] + seg[2*i+1];
    int j = 0;
    while(true&&k!=1){
        ll le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        ll ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j]);
        lazy[i].second.pb(le+ri);
        if(le+ri==0)break; 
        j++;
    }   
    lazy[i].first={-1,0};
}

void push(int i,int l,int r){
    if(k==1)return;
    auto [ind,add] = lazy[i].first;
    if(!add)return;
    ind = min(sz(lazy[i].second)-1,ind+add);
    seg[i] = lazy[i].second[ind];
    lazy[i].first.second = 0;
    if(l==r)return;
    lazy[2*i].first.second+=add;
    lazy[2*i+1].first.second+=add;
}

void update(int i,int l,int r,int x,ll d){
    if(k!=1)push(i,l,r);
    if(l>x||r<x)return;
    if(l==r){
        seg[i] = d;
        lazy[i].second.clear();
        ll tmp = d;
        while(true&&k!=1){lazy[i].second.pb(tmp/k);if(!(tmp/k))break;tmp/=k;}
        lazy[i].first={-1,0};
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,d);
    update(2*i+1,md+1,r,x,d);
    lazy[i].second.clear();
    int j = 0;
    while(true&&k!=1){
        ll le = (j>=sz(lazy[2*i].second) ? 0 : lazy[2*i].second[j]);
        ll ri = (j>=sz(lazy[2*i+1].second) ? 0 : lazy[2*i+1].second[j]);
        lazy[i].second.pb(le+ri);
        j++;
        if(le+ri==0)break; 
    }   
    seg[i] = seg[2*i] + seg[2*i+1];
    lazy[i].first={-1,0};
}

void update2(int i,int l,int r,int x,int y){
    if(k!=1)push(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i].first.second++;
        push(i,l,r);
        return;
    }
    int md = (l+r)/2;
    update2(2*i,l,md,x,y);
    update2(2*i+1,md+1,r,x,y);
    seg[i] = seg[2*i] + seg[2*i+1];
}


ll query(int i,int l,int r,int x,int y){
    if(k!=1)push(i,l,r);
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return seg[i];
    int md = (l+r)/2;
    return query(2*i,l,md,x,y) + query(2*i+1,md+1,r,x,y);
}

int main(){_
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++)cin>>v[i];
    build(1,1,n);
    while(q--){
        int t,a;
        ll b;cin>>t>>a>>b;
        if(t==1){   
            update(1,1,n,a,b);
        }else if(t==2){
            if(k!=1)update2(1,1,n,a,b);
        }else{
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
}

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