oj.uz

Submission #828077

# Submission time Handle Problem Language Result Execution time Memory
828077 2023-08-17T03:46:30 Z trucmai Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 81 ms 13416 KB 
#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; 
        if(lz[i].a == 0) tr[i] = lz[i].b; 
        else tr[i] = tr[i]/lz[i].a;
        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,0,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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7540 KB Output is correct
2 Correct 47 ms 5648 KB Output is correct
3 Correct 55 ms 10076 KB Output is correct
4 Correct 57 ms 12844 KB Output is correct
5 Correct 69 ms 13384 KB Output is correct
6 Correct 74 ms 13380 KB Output is correct
7 Correct 66 ms 13416 KB Output is correct
8 Correct 65 ms 13412 KB Output is correct
9 Correct 63 ms 13280 KB Output is correct
10 Correct 63 ms 13240 KB Output is correct
11 Correct 81 ms 13220 KB Output is correct
12 Correct 72 ms 13292 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 7176 KB Output isn't correct
2 Halted 0 ms 0 KB -