oj.uz

Submission #125025

# Submission time Handle Problem Language Result Execution time Memory
125025 2019-07-04T11:51:05 Z trinhhung Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 272 ms 6052 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 5;
int n, m, q;
int a[N], node[405000];

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){
    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){
    if(node[i] == 0 || m == 1) return;
    if(l > r || l > b || r < a) return;
    if(l == r){
        node[i] /= m;
        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){
    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 <= 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 476 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 508 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2268 KB Output is correct
2 Correct 54 ms 2040 KB Output is correct
3 Correct 50 ms 3320 KB Output is correct
4 Correct 64 ms 3576 KB Output is correct
5 Correct 82 ms 3676 KB Output is correct
6 Correct 75 ms 3704 KB Output is correct
7 Correct 76 ms 3676 KB Output is correct
8 Correct 76 ms 3704 KB Output is correct
9 Correct 71 ms 3704 KB Output is correct
10 Correct 71 ms 3704 KB Output is correct
11 Correct 74 ms 3704 KB Output is correct
12 Correct 74 ms 3692 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 632 KB Output is correct
2 Correct 16 ms 2040 KB Output is correct
3 Correct 22 ms 2168 KB Output is correct
4 Correct 57 ms 2268 KB Output is correct
5 Correct 73 ms 4728 KB Output is correct
6 Correct 78 ms 4668 KB Output is correct
7 Correct 70 ms 4856 KB Output is correct
8 Correct 79 ms 4728 KB Output is correct
9 Correct 67 ms 4476 KB Output is correct
10 Correct 67 ms 4572 KB Output is correct
11 Correct 67 ms 4472 KB Output is correct
12 Correct 67 ms 4600 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 3056 KB Output is correct
2 Correct 106 ms 3908 KB Output is correct
3 Correct 124 ms 3064 KB Output is correct
4 Correct 129 ms 3148 KB Output is correct
5 Correct 155 ms 5880 KB Output is correct
6 Correct 177 ms 6052 KB Output is correct
7 Correct 147 ms 5880 KB Output is correct
8 Correct 212 ms 5984 KB Output is correct
9 Correct 187 ms 5880 KB Output is correct
10 Correct 208 ms 5988 KB Output is correct
11 Correct 159 ms 5880 KB Output is correct
12 Correct 272 ms 5812 KB Output is correct