oj.uz

답안 #445793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445793 2021-07-19T14:58:22 Z JovanB Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 77 ms 7364 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;
    assert(k == 1);
    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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 4028 KB Output is correct
2 Correct 51 ms 3780 KB Output is correct
3 Correct 47 ms 6944 KB Output is correct
4 Correct 61 ms 7236 KB Output is correct
5 Correct 77 ms 7268 KB Output is correct
6 Correct 74 ms 7328 KB Output is correct
7 Correct 75 ms 7336 KB Output is correct
8 Correct 73 ms 7248 KB Output is correct
9 Correct 67 ms 7244 KB Output is correct
10 Correct 69 ms 7268 KB Output is correct
11 Correct 69 ms 7364 KB Output is correct
12 Correct 70 ms 7284 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -