oj.uz

Submission #675963

# Submission time Handle Problem Language Result Execution time Memory
675963 2022-12-28T16:32:17 Z Ronin13 Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 3342 ms 14700 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){
            if(k == 1) continue;
            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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 10912 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 631 ms 12436 KB Output is correct
2 Correct 563 ms 11948 KB Output is correct
3 Correct 1298 ms 12452 KB Output is correct
4 Correct 736 ms 11960 KB Output is correct
5 Correct 1280 ms 12840 KB Output is correct
6 Correct 1430 ms 12800 KB Output is correct
7 Correct 1096 ms 13972 KB Output is correct
8 Correct 2137 ms 14408 KB Output is correct
9 Correct 1947 ms 14432 KB Output is correct
10 Correct 2223 ms 14700 KB Output is correct
11 Correct 1254 ms 14456 KB Output is correct
12 Correct 3342 ms 14480 KB Output is correct