oj.uz

Submission #828083

# Submission time Handle Problem Language Result Execution time Memory
828083 2023-08-17T03:55:09 Z trucmai Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 64 ms 11004 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; 
        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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5724 KB Output is correct
2 Correct 50 ms 4036 KB Output is correct
3 Correct 43 ms 8528 KB Output is correct
4 Correct 53 ms 10700 KB Output is correct
5 Correct 63 ms 10940 KB Output is correct
6 Correct 64 ms 10944 KB Output is correct
7 Correct 64 ms 10956 KB Output is correct
8 Correct 64 ms 10956 KB Output is correct
9 Correct 62 ms 10956 KB Output is correct
10 Correct 61 ms 11004 KB Output is correct
11 Correct 63 ms 11004 KB Output is correct
12 Correct 61 ms 10956 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 10964 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -