Submission #1156806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156806		Hamed_Ghaffari	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	187 ms	5448 KiB

sterilizing

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

using ll = long long;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 1e5+5;

int n, a[MXN], seg[MXN<<2], lz[MXN<<2];
ll sum[MXN<<2];

inline void pull(int id) {
    seg[id] = (seg[lc]==seg[rc] ? seg[lc] : -1);
    sum[id] = sum[lc] + sum[rc];
}
void build(int l=1, int r=n+1, int id=1) {
    lz[id] = -1;
    if(r-l == 1) {
        seg[id] = sum[id] = a[l];
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    pull(id);
}
inline void apply(int x, int l, int r, int id) {
    seg[id] = x;
    sum[id] = ll(r-l)*x;
    lz[id] = x;
}
inline void shift(int l, int r, int id) {
    if(r-l>1 && lz[id]!=-1) {
        apply(lz[id], l, mid, lc);
        apply(lz[id], mid, r, rc);
    }
    lz[id] = -1;
}
void ass(int s, int e, int x, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) {
        apply(x, l, r, id);
        return;
    }
    shift(l, r, id);
    if(s<mid) ass(s, e, x, l, mid, lc);
    if(e>mid) ass(s, e, x, mid, r, rc);
    pull(id);
}
void upd(int s, int e, int x, int l=1, int r=n+1, int id=1) {
    if(s>=r || l>=e || x==1) return;
    if(s<=l && r<=e && seg[id]!=-1) {
        apply(seg[id]/x, l, r, id);
        return;
    }
    shift(l, r, id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
    pull(id);
}
ll get(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s>=r || l>=e) return 0ll;
    if(s<=l && r<=e) return sum[id];
    shift(l, r, id);
    return get(s, e, l, mid, lc) + get(s, e, mid, r, rc);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int q, k;
    cin >> n >> q >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
    build();
    while(q--) {
        int x, y, z;
        cin >> x >> y >> z;
        if(x==1) {
            ass(y, y+1, z);
        }
        if(x==2) {
            upd(y, z+1, k);
        }
        if(x==3) {
            cout << get(y, z+1) << '\n';
        }
    }
    return 0;
}

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