oj.uz

Submission #445792

# Submission time Handle Problem Language Result Execution time Memory
445792 2021-07-19T14:57:08 Z JovanB Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 92 ms 7388 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);
    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;
            assert(0);
            //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 Runtime error 2 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4148 KB Output is correct
2 Correct 52 ms 3796 KB Output is correct
3 Correct 48 ms 7108 KB Output is correct
4 Correct 61 ms 7236 KB Output is correct
5 Correct 78 ms 7360 KB Output is correct
6 Correct 76 ms 7340 KB Output is correct
7 Correct 81 ms 7388 KB Output is correct
8 Correct 92 ms 7312 KB Output is correct
9 Correct 69 ms 7348 KB Output is correct
10 Correct 75 ms 7340 KB Output is correct
11 Correct 71 ms 7348 KB Output is correct
12 Correct 75 ms 7320 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1356 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 7180 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -