oj.uz

Submission #675960

# Submission time Handle Problem Language Result Execution time Memory
675960 2022-12-28T16:23:11 Z Ronin13 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 15348 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 1e5 + 1;
vector <pll> t(4 * nmax);
vector <ll> T(4 * nmax);
vector <ll> a(nmax);

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

void update(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v].f = T[v] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
    T[v] = T[2 * v] + T[2 * v + 1];
}

pll get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return {0, 0};
    if(l >= st && r <= fin)
        return t[v];
    int m = (l + r) /2;
    pll x = get(2 * v, l, m, st, fin);
    pll y = get(2 * v + 1, m + 1, r, st, fin);
    return max(x, y);
}
ll get1(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin)
        return T[v];
    int m = (l + r) /2;
    ll x = get1(2 * v, l, m, st, fin);
    ll y = get1(2 * v + 1, m + 1, r, st, fin);
    return x + y;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q, k; cin >> n >> q >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build(1,1, n);
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int pos, val; cin >> pos >> val;
            update(1, 1, n, pos, val);
            continue;
        }
        if(t == 2){
            vector <pii> vec;
            int l, r; cin >> l >> r;
            while(true){
                pll u = get(1, 1, n, l, r);
                if(!u.f) break;
                u.f /= k;
                update(1, 1, n, u.s, 0);
                vec.pb(u);
            }
            for(auto to : vec)
                update(1, 1, n, to.s, to.f);
            continue;
        }
        if(t == 3){
            int l, r; cin >> l >> r;
            cout << get1(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10500 KB Output is correct
2 Correct 36 ms 10452 KB Output is correct
3 Correct 13 ms 10528 KB Output is correct
4 Correct 36 ms 10580 KB Output is correct
5 Correct 37 ms 10580 KB Output is correct
6 Correct 24 ms 10580 KB Output is correct
7 Correct 32 ms 10676 KB Output is correct
8 Correct 38 ms 10652 KB Output is correct
9 Correct 46 ms 10668 KB Output is correct
10 Correct 29 ms 10656 KB Output is correct
11 Correct 29 ms 10580 KB Output is correct
12 Correct 32 ms 10640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 13128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 13272 KB Output is correct
2 Correct 548 ms 12848 KB Output is correct
3 Correct 1281 ms 12780 KB Output is correct
4 Correct 739 ms 12920 KB Output is correct
5 Correct 1062 ms 14236 KB Output is correct
6 Correct 1377 ms 14156 KB Output is correct
7 Correct 1012 ms 15252 KB Output is correct
8 Correct 1985 ms 15116 KB Output is correct
9 Correct 1851 ms 15236 KB Output is correct
10 Correct 2300 ms 15348 KB Output is correct
11 Correct 1369 ms 15300 KB Output is correct
12 Correct 3428 ms 15268 KB Output is correct