oj.uz

Submission #445780

# Submission time Handle Problem Language Result Execution time Memory
445780 2021-07-19T14:45:14 Z JovanB Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 151 ms 9796 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;
    return;
}

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);
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 332 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 67 ms 5844 KB Output is correct
2 Correct 60 ms 5396 KB Output is correct
3 Correct 54 ms 8644 KB Output is correct
4 Correct 68 ms 9320 KB Output is correct
5 Correct 89 ms 9740 KB Output is correct
6 Correct 84 ms 9796 KB Output is correct
7 Correct 100 ms 9668 KB Output is correct
8 Correct 97 ms 9752 KB Output is correct
9 Correct 77 ms 9568 KB Output is correct
10 Correct 79 ms 9592 KB Output is correct
11 Correct 86 ms 9684 KB Output is correct
12 Correct 77 ms 9540 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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