oj.uz

Submission #198655

# Submission time Handle Problem Language Result Execution time Memory
198655 2020-01-27T08:38:22 Z osaaateiasavtnl Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 280 ms 8124 KB 
#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 && 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Incorrect 6 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1144 KB Output is correct
2 Correct 25 ms 3192 KB Output is correct
3 Correct 31 ms 3192 KB Output is correct
4 Correct 61 ms 2808 KB Output is correct
5 Correct 97 ms 6776 KB Output is correct
6 Correct 88 ms 6776 KB Output is correct
7 Incorrect 102 ms 7160 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 4472 KB Output is correct
2 Correct 111 ms 4728 KB Output is correct
3 Correct 119 ms 4064 KB Output is correct
4 Correct 138 ms 3624 KB Output is correct
5 Correct 171 ms 8036 KB Output is correct
6 Correct 187 ms 7928 KB Output is correct
7 Correct 168 ms 8124 KB Output is correct
8 Correct 213 ms 8056 KB Output is correct
9 Correct 188 ms 7928 KB Output is correct
10 Correct 228 ms 8016 KB Output is correct
11 Correct 164 ms 7800 KB Output is correct
12 Correct 280 ms 7896 KB Output is correct