oj.uz

Submission #125022

# Submission time Handle Problem Language Result Execution time Memory
125022 2019-07-04T11:31:16 Z trinhhung Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 196 ms 6908 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 5;
int n, m, q;
int a[N], node[4 * N], lazy[4 * N];

void down(int i, int l, int r){
    if(l > r) return;
    node[i] /= lazy[i];
    if(l == r){
        lazy[i] = 1;
        return;
    }
    lazy[i * 2] *= lazy[i];
    lazy[i * 2 + 1] *= lazy[i];
    lazy[i] = 1;
}

void build_tree(int i, int l, int r){
    if(l > r) return;
    if(l == r){
        node[i] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build_tree(i * 2, l, mid);
    build_tree(i * 2 + 1, mid + 1, r);
    node[i] = node[i * 2] + node[i * 2 + 1];
}

void update(int i, int l, int r, int pos, int val){
    down(i, l, r);
    if(l > r || l > pos || r < pos) return;
    if(l == r){
        if(l == pos)
            node[i] = val;
        return;
    }
    int mid = (l + r) / 2;
    update(i * 2, l, mid, pos, val);
    update(i * 2 + 1, mid + 1, r, pos, val);
    node[i] = node[i * 2] + node[i * 2 + 1];
}

void update_2(int i, int l, int r, int a, int b){
    down(i, l, r);
    if(l > r || l > b || r < a) return;
    if(l >= a && r <= b){
        lazy[i] *= m;
        down(i, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update_2(i * 2, l, mid, a, b);
    update_2(i * 2 + 1, mid + 1, r, a, b);
    node[i] = node[i * 2] + node[i * 2 + 1];
}

int get(int i, int l, int r, int a, int b){
    down(i, l, r);
    if(l > r || l > b || r < a) return 0;
    if(l >= a && r <= b) return node[i];
    int mid = (l + r) / 2;
    return get(i * 2, l, mid, a, b) + get(i * 2 + 1, mid + 1, r, a, b);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> m;
    for(int i = 1; i <= 4 * n; ++ i) lazy[i] = 1;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    build_tree(1, 1, n);
    while(q --){
        int x, y, z;
        cin >> x >> y >> z;
        if(x == 1)
            update(1, 1, n, y, z);
        else if(x == 2)
            update_2(1, 1, n, y, z);
        else
            cout << get(1, 1, n , y, z) << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 3832 KB Output is correct
2 Correct 140 ms 3100 KB Output is correct
3 Correct 120 ms 5752 KB Output is correct
4 Correct 167 ms 6612 KB Output is correct
5 Correct 196 ms 6776 KB Output is correct
6 Correct 193 ms 6776 KB Output is correct
7 Correct 195 ms 6904 KB Output is correct
8 Correct 193 ms 6768 KB Output is correct
9 Correct 193 ms 6908 KB Output is correct
10 Correct 189 ms 6852 KB Output is correct
11 Correct 188 ms 6872 KB Output is correct
12 Correct 187 ms 6776 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 6648 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -