oj.uz

Submission #827648

# Submission time Handle Problem Language Result Execution time Memory
827648 2023-08-16T15:44:04 Z trucmai Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 91 ms 13388 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(0,0));
    }
    void push(ll i,ll l,ll r){
        if(lz[i].a == 0 && lz[i].b == 0) return; 
        if(lz[i].a == 0) tr[i] = lz[i].b; 
        else tr[i] = tr[i]/lz[i].a + lz[i].b;
        if(l != r){
            lz[2*i] = lz[i];
            lz[2*i+1] = lz[i];
        }
        lz[i] = node(0,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 2 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 74 ms 7668 KB Output is correct
2 Correct 62 ms 5744 KB Output is correct
3 Correct 56 ms 10148 KB Output is correct
4 Correct 76 ms 12876 KB Output is correct
5 Correct 88 ms 13364 KB Output is correct
6 Correct 91 ms 13388 KB Output is correct
7 Correct 90 ms 13340 KB Output is correct
8 Correct 85 ms 13356 KB Output is correct
9 Correct 74 ms 13188 KB Output is correct
10 Correct 77 ms 13268 KB Output is correct
11 Correct 75 ms 13276 KB Output is correct
12 Correct 74 ms 13256 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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