oj.uz

Submission #83822

# Submission time Handle Problem Language Result Execution time Memory
83822 2018-11-11T05:03:23 Z mra2322001 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 384 ms 41644 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, ma[N*4], a[N], ki, q;
ll t[4*N];
ll res = 0;

void build(int k, int l, int r){
    if(l==r){
        ma[k] = t[k] = a[l];
        return ;
    }
    int m = (l + r)/2;
    build(k*2, l, m);
    build(k*2 + 1, m + 1, r);
    t[k] = t[2*k] + t[2*k + 1];
    ma[k] = max(ma[2*k], ma[2*k+1]);
}

void adjust(int k, int l, int r, int i, int x){
    if(l==r){
        t[k] = ma[k] = x;
        return ;
    }
    int m = (l + r)/2;
    if(i <= m) adjust(k*2, l, m, i, x);
    else adjust(k*2 + 1, m + 1, r, i, x);
    t[k] = t[2*k] + t[2*k + 1];
    ma[k] = max(ma[2*k], ma[2*k + 1]);
}

void get1(int k, int l, int r, int i, int j){
    if(r < i || l > j) return ;
    if(l >= i && r <= j){
        res += t[k];
        return ;
    }
    int m = (l + r)/2;
    get1(k*2, l, m, i, j);
    get1(k*2 + 1, m + 1, r, i, j);
}

void divide(int k, int l, int r, int i, int j){
    if(r < i || l > j) return ;
    if(l >= i && r <= j){
        if(ma[k]==0) return ;
        if(l==r){
            t[k] = ma[k] = t[k]/ki;
            return ;
        }
    }
    int m = (l + r)/2;
    divide(k*2, l, m, i, j);
    divide(k*2 + 1, m + 1, r, i, j);
    t[k] = t[2*k] + t[2*k + 1];
    ma[k] = max(ma[2*k], ma[2*k + 1]);
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> q >> ki;
    f1(i, n) cin >> a[i];

    build(1, 1, n);
    while(q--){
        int type; cin >> type;
        if(type==1){
            int x, y; cin >> x >> y;
            adjust(1, 1, n, x, y);
        }
        if(type==2){
            int l, r; cin >> l >> r;
            if(ki != 1) divide(1, 1, n, l, r);
        }
        if(type==3){
            int l, r; cin >> l >> r;
            res = 0;
            get1(1, 1, n, l, r);
            cout << res << "\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 8 ms 732 KB Output is correct
5 Correct 9 ms 772 KB Output is correct
6 Correct 10 ms 852 KB Output is correct
7 Correct 10 ms 1048 KB Output is correct
8 Correct 8 ms 1176 KB Output is correct
9 Correct 9 ms 1176 KB Output is correct
10 Correct 8 ms 1244 KB Output is correct
11 Correct 8 ms 1312 KB Output is correct
12 Correct 8 ms 1380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 3496 KB Output is correct
2 Correct 98 ms 3496 KB Output is correct
3 Correct 81 ms 4916 KB Output is correct
4 Correct 107 ms 5172 KB Output is correct
5 Correct 127 ms 5248 KB Output is correct
6 Correct 131 ms 5248 KB Output is correct
7 Correct 140 ms 5276 KB Output is correct
8 Correct 131 ms 5300 KB Output is correct
9 Correct 122 ms 5300 KB Output is correct
10 Correct 136 ms 5300 KB Output is correct
11 Correct 133 ms 5300 KB Output is correct
12 Correct 120 ms 5300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5300 KB Output is correct
2 Correct 26 ms 5300 KB Output is correct
3 Correct 38 ms 5300 KB Output is correct
4 Correct 139 ms 5300 KB Output is correct
5 Correct 145 ms 8164 KB Output is correct
6 Correct 149 ms 9720 KB Output is correct
7 Correct 126 ms 11120 KB Output is correct
8 Correct 161 ms 12604 KB Output is correct
9 Correct 137 ms 13712 KB Output is correct
10 Correct 137 ms 15112 KB Output is correct
11 Correct 139 ms 16260 KB Output is correct
12 Correct 140 ms 17584 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 17584 KB Output is correct
2 Correct 171 ms 17752 KB Output is correct
3 Correct 174 ms 18764 KB Output is correct
4 Correct 220 ms 19728 KB Output is correct
5 Correct 235 ms 24764 KB Output is correct
6 Correct 270 ms 27312 KB Output is correct
7 Correct 239 ms 29692 KB Output is correct
8 Correct 311 ms 32276 KB Output is correct
9 Correct 286 ms 34600 KB Output is correct
10 Correct 304 ms 36884 KB Output is correct
11 Correct 249 ms 39216 KB Output is correct
12 Correct 384 ms 41644 KB Output is correct