Submission #445794

#	Time	Username	Problem	Language	Result	Execution time	Memory
445794		JovanB	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	557 ms	9668 KiB

sterilizing

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

using ll = long long;
using ld = long double;

const int N = 100000;

struct Segment{
    ll sum;
    int lazy, mn, mx;
} seg[4*N+5];

int a[N+5];

void propagate(int node, int l, int r){
    if(seg[node].lazy == -1) return;
    seg[node].mn = seg[node].mx = seg[node].lazy;
    seg[node].sum = 1LL*(r-l+1)*seg[node].lazy;
    if(l == r){
        seg[node].lazy = -1;
        return;
    }
    seg[node*2].lazy = seg[node].lazy;
    seg[node*2+1].lazy = seg[node].lazy;
    seg[node].lazy = -1;
}

void mrg(int node){
    seg[node].sum = seg[node*2].sum + seg[node*2+1].sum;
    seg[node].mn = min(seg[node*2].mn, seg[node*2+1].mn);
    seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
}

void init(int node, int l, int r){
    seg[node].lazy = -1;
    if(l == r){
        seg[node].mn = seg[node].mx = seg[node].sum = a[l];
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    mrg(node);
}

void upd_point(int node, int l, int r, int x, int val){
    propagate(node, l, r);
    if(l == r){
        seg[node].mn = seg[node].mx = seg[node].sum = val;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd_point(node*2, l, mid, x, val);
    else upd_point(node*2+1, mid+1, r, x, val);
    propagate(node*2, l, mid);
    propagate(node*2+1, mid+1, r);
    mrg(node);
}

void spray(int node, int l, int r, int tl, int tr, int k){
    propagate(node, l, r);
    if(tl > r || l > tr || seg[node].mx == 0) return;
    if(tl <= l && r <= tr && seg[node].mn/k == seg[node].mx/k){
        seg[node].lazy = seg[node].mn/k;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    spray(node*2, l, mid, tl, tr, k);
    spray(node*2+1, mid+1, r, tl, tr, k);
    mrg(node);
}

ll query(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr) return 0;
    if(tl <= l && r <= tr) return seg[node].sum;
    int mid = (l+r)/2;
    return query(node*2, l, mid, tl, tr) + query(node*2+1, mid+1, r, tl, tr);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, qrs, k;
    cin >> n >> qrs >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
    init(1, 1, n);
    while(qrs--){
        int typ;
        cin >> typ;
        if(typ == 1){
            int x, y;
            cin >> x >> y;
            upd_point(1, 1, n, x, y);
        }
        else if(typ == 2){
            int l, r;
            cin >> l >> r;
            if(k == 1) continue;
            spray(1, 1, n, l, r, k);
        }
        else{
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

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