Submission #198656

#	Time	Username	Problem	Language	Result	Execution time	Memory
198656		osaaateiasavtnl	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	280 ms	8292 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7;
int a[N];
int mx[N << 2], sum[N << 2];
int n, q, k;
void relax(int v) {
    mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
    sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
}   
void upd(int v, int tl, int tr, int i, int x) {
    if (tl == tr) {
        mx[v] = sum[v] = x;
        return;
    }   
    int tm = (tl + tr) >> 1;
    if (i <= tm)
        upd(v * 2 + 1, tl, tm, i, x);
    else
        upd(v * 2 + 2, tm + 1, tr, i, x);
    relax(v);
}   
void del(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl || mx[v] == 0)
        return;
    if (tl == tr) {
        mx[v] = sum[v] = mx[v] / k;
        return;
    }   
    int tm = (tl + tr) >> 1;
    del(v * 2 + 1, tl, tm, l, r); del(v * 2 + 2, tm + 1, tr, l, r);
    relax(v);        
}   
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl)
        return 0;
    if (l <= tl && tr <= r)
        return sum[v];
    int tm = (tl + tr) >> 1;
    return get(v * 2 + 1, tl, tm, l, r) + get(v * 2 + 2, tm + 1, tr, l, r);
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> q >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        upd(0, 0, n - 1, i, a[i]);
    }    
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) 
            upd(0, 0, n - 1, x - 1, y);
        else if (t == 2) {
            if (k > 1)
                del(0, 0, n - 1, x - 1, y - 1);
        }
        else
            cout << get(0, 0, n - 1, x - 1, y - 1) << '\n';
        /*
        for (int i = 0; i < n; ++i)
            cout << get(0, 0, n - 1, i, i) << ' ';
        cout << '\n';
        */
    }
}   

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75