oj.uz

Submission #125021

# Submission time Handle Problem Language Result Execution time Memory
125021 2019-07-04T11:30:15 Z trinhhung Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 220 ms 9464 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 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 7 ms 508 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 165 ms 3900 KB Output is correct
2 Correct 141 ms 4644 KB Output is correct
3 Correct 125 ms 7404 KB Output is correct
4 Correct 160 ms 8796 KB Output is correct
5 Correct 220 ms 9272 KB Output is correct
6 Correct 213 ms 9464 KB Output is correct
7 Correct 195 ms 9372 KB Output is correct
8 Correct 194 ms 9336 KB Output is correct
9 Correct 190 ms 9080 KB Output is correct
10 Correct 189 ms 9080 KB Output is correct
11 Correct 190 ms 9208 KB Output is correct
12 Correct 191 ms 9076 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 888 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 20 ms 6652 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -