oj.uz

Submission #125023

# Submission time Handle Problem Language Result Execution time Memory
125023 2019-07-04T11:32:49 Z trinhhung Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 197 ms 6904 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[405000], lazy[405000];

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 164 ms 3728 KB Output is correct
2 Correct 142 ms 3128 KB Output is correct
3 Correct 124 ms 5828 KB Output is correct
4 Correct 158 ms 6648 KB Output is correct
5 Correct 194 ms 6776 KB Output is correct
6 Correct 196 ms 6856 KB Output is correct
7 Correct 197 ms 6756 KB Output is correct
8 Correct 196 ms 6828 KB Output is correct
9 Correct 188 ms 6840 KB Output is correct
10 Correct 189 ms 6904 KB Output is correct
11 Correct 188 ms 6904 KB Output is correct
12 Correct 190 ms 6776 KB Output is correct

Subtask #3
0 / 10.0

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