oj.uz

Submission #198656

# Submission time Handle Problem Language Result Execution time Memory
198656 2020-01-27T08:39:38 Z osaaateiasavtnl Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 280 ms 8292 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) {
            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.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3252 KB Output is correct
2 Correct 64 ms 4728 KB Output is correct
3 Correct 69 ms 7036 KB Output is correct
4 Correct 87 ms 7812 KB Output is correct
5 Correct 96 ms 8184 KB Output is correct
6 Correct 98 ms 8092 KB Output is correct
7 Correct 103 ms 8292 KB Output is correct
8 Correct 94 ms 8184 KB Output is correct
9 Correct 95 ms 7988 KB Output is correct
10 Correct 87 ms 8056 KB Output is correct
11 Correct 87 ms 8056 KB Output is correct
12 Correct 86 ms 8056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 760 KB Output is correct
2 Correct 23 ms 2936 KB Output is correct
3 Correct 28 ms 2808 KB Output is correct
4 Correct 66 ms 1784 KB Output is correct
5 Correct 90 ms 5240 KB Output is correct
6 Correct 94 ms 5368 KB Output is correct
7 Correct 89 ms 5680 KB Output is correct
8 Correct 88 ms 6776 KB Output is correct
9 Correct 82 ms 6520 KB Output is correct
10 Correct 82 ms 6524 KB Output is correct
11 Correct 84 ms 6520 KB Output is correct
12 Correct 81 ms 6524 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3056 KB Output is correct
2 Correct 114 ms 3064 KB Output is correct
3 Correct 116 ms 2936 KB Output is correct
4 Correct 137 ms 1912 KB Output is correct
5 Correct 157 ms 5496 KB Output is correct
6 Correct 174 ms 5496 KB Output is correct
7 Correct 159 ms 5496 KB Output is correct
8 Correct 214 ms 5624 KB Output is correct
9 Correct 204 ms 5624 KB Output is correct
10 Correct 211 ms 5624 KB Output is correct
11 Correct 168 ms 5624 KB Output is correct
12 Correct 280 ms 5680 KB Output is correct