Submission #828083

#	Time	Username	Problem	Language	Result	Execution time	Memory
828083		trucmai	Sterilizing Spray (JOI15_sterilizing)	C++17	10 / 100	64 ms	11004 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<ll>
#define pi pair<ll,ll>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'

const int N = 1e6 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,q,k,a[N];
struct segtree{
    struct node{
        ll a,b; 
        node(){}
        node(ll a,ll b):a(a),b(b){}    
    };
    ll n;
    vector<ll>tr; vector<node>lz; 
    segtree(){}
    void init(ll sz){
        n = sz;
        tr.resize(4*n+5);
        lz = vector<node>(4*n+5,node(1,0));
    }
    void push(ll i,ll l,ll r){
        if(lz[i].a == 1 && lz[i].b == 0) return; 
        tr[i] = tr[i]/lz[i].a + (r-l+1)*lz[i].b;
        if(l != r){
            lz[2*i] = node(lz[2*i].a*lz[i].a,lz[i].a*lz[2*i+1].b + lz[i].b);
            lz[2*i+1] = node(lz[2*i+1].a*lz[i].a,lz[i].a*lz[2*i+1].b + lz[i].b);
        }
        lz[i] = node(1,0);
    }
    void build(ll i,ll l,ll r){
        if(l == r){
            tr[i] = a[l]; 
            return;
        }
        ll m = (r+l)>>1;
        build(2*i,l,m); build(2*i+1,m+1,r);
        tr[i] = tr[2*i] + tr[2*i+1];
    }
    void upd(ll i,ll l,ll r,ll ql,ll qr,node val){ 
        push(i,l,r);
        if(l > qr || r < ql) return;
        if(ql <= l && r <= qr){
            lz[i] = val; 
            push(i,l,r); 
            return;
        }
        ll m = (r+l)>>1;
        upd(2*i,l,m,ql,qr,val); upd(2*i+1,m+1,r,ql,qr,val); 
        tr[i] = tr[2*i] + tr[2*i+1];
    }
    ll get(ll i,ll l,ll r,ll ql,ll qr){
        push(i,l,r);
        if(l > qr || r < ql) return 0;
        if(ql <= l && r <= qr) return tr[i]; 
        ll m = (r+l) >> 1; 
        ll left = get(2*i,l,m,ql,qr),
            right = get(2*i+1,m+1,r,ql,qr);
        return left + right;
    } 
    void build(){build(1,1,n);}
    void upd(ll l,ll r,ll a,ll b){upd(1,1,n,l,r,node(a,b));}
    ll get(ll l,ll r){return get(1,1,n,l,r);}
}st;

void solve(){
    cin>>n>>q>>k;
    for(ll i = 1;i <= n;++i) cin>>a[i]; 
    st.init(n); st.build();
    while(q--){
        ll type,t,u; cin>>type>>t>>u;
        if(type == 1) st.upd(t,t,INF,u);
        else if(type == 2) st.upd(t,u,k,0);
        else cout<<st.get(t,u)<<endl;
    }    
}

signed main(){
    cin.tie(0); cout.tie(0); 
    ios_base::sync_with_stdio(false);
    ll t = 1; //cin>>t;
    while(t--) solve(); 
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

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