oj.uz

Submission #83821

# Submission time Handle Problem Language Result Execution time Memory
83821 2018-11-11T04:56:42 Z mra2322001 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 166 ms 31260 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(ma[k] < ki){
            ma[k] = 0;
            t[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
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 4652 KB Output is correct
2 Correct 121 ms 6232 KB Output is correct
3 Correct 96 ms 9572 KB Output is correct
4 Correct 109 ms 11956 KB Output is correct
5 Correct 166 ms 14628 KB Output is correct
6 Correct 134 ms 17052 KB Output is correct
7 Correct 133 ms 19660 KB Output is correct
8 Correct 134 ms 22008 KB Output is correct
9 Correct 121 ms 24240 KB Output is correct
10 Correct 124 ms 26648 KB Output is correct
11 Correct 125 ms 28948 KB Output is correct
12 Correct 139 ms 31148 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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