oj.uz

Submission #445794

# Submission time Handle Problem Language Result Execution time Memory
445794 2021-07-19T15:01:16 Z JovanB Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 557 ms 9668 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 8 ms 556 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 6 ms 600 KB Output is correct
9 Correct 8 ms 588 KB Output is correct
10 Correct 6 ms 520 KB Output is correct
11 Correct 6 ms 588 KB Output is correct
12 Correct 7 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4000 KB Output is correct
2 Correct 61 ms 3688 KB Output is correct
3 Correct 59 ms 6976 KB Output is correct
4 Correct 69 ms 7212 KB Output is correct
5 Correct 87 ms 7260 KB Output is correct
6 Correct 106 ms 7348 KB Output is correct
7 Correct 83 ms 7284 KB Output is correct
8 Correct 87 ms 7304 KB Output is correct
9 Correct 95 ms 7364 KB Output is correct
10 Correct 90 ms 7348 KB Output is correct
11 Correct 82 ms 7264 KB Output is correct
12 Correct 79 ms 7248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 816 KB Output is correct
2 Correct 17 ms 3788 KB Output is correct
3 Correct 25 ms 3984 KB Output is correct
4 Correct 70 ms 3292 KB Output is correct
5 Correct 87 ms 8260 KB Output is correct
6 Correct 87 ms 8256 KB Output is correct
7 Correct 78 ms 8388 KB Output is correct
8 Correct 93 ms 8276 KB Output is correct
9 Correct 82 ms 8144 KB Output is correct
10 Correct 77 ms 8188 KB Output is correct
11 Correct 79 ms 8136 KB Output is correct
12 Correct 79 ms 8132 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 3860 KB Output is correct
2 Correct 167 ms 5504 KB Output is correct
3 Correct 219 ms 4836 KB Output is correct
4 Correct 221 ms 3976 KB Output is correct
5 Correct 244 ms 9564 KB Output is correct
6 Correct 291 ms 9536 KB Output is correct
7 Correct 242 ms 9668 KB Output is correct
8 Correct 378 ms 9592 KB Output is correct
9 Correct 354 ms 9524 KB Output is correct
10 Correct 402 ms 9396 KB Output is correct
11 Correct 278 ms 9416 KB Output is correct
12 Correct 557 ms 9392 KB Output is correct