oj.uz

Submission #868016

# Submission time Handle Problem Language Result Execution time Memory
868016 2023-10-30T08:20:37 Z tienbinh Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1018 ms 138504 KB 
#include <bits/stdc++.h>

using namespace std;
#define name ""
#define int long long
const int N = 5e5 + 7;
int n, q, k, a[N];

struct Node{
    basic_string<int>val;
    Node() {}
    Node(int x) {
        // Code here
        while(x > 0){
            val += (x % k);
            x /= k;
        }
    }
    Node(Node l, Node r) {
        // Code here
        for(int i = 0 ; i < (int)max(l.val.size() , r.val.size()); i++) 
            val += (i < (int)l.val.size() ? l.val[i] : 0 ) + (i < (int)r.val.size() ? r.val[i] : 0);
    }
    explicit operator long long() {
        long long res = 0;
        reverse(val.begin(), val.end());
        for (int i : val) res = res * k + i;
        reverse(val.begin(), val.end());
        return res;
    }
} st[N << 2];

struct Update {
    int cnt_div = 0;
    Update() {}
    Update(int x) : cnt_div(x) {}
    Update(Update l, Update r) {
        cnt_div = l.cnt_div + r.cnt_div;
    }
} lazy[N << 2];

Node identity_value() { return Node(); }
Node merge(Node a, Node b) { return Node(a, b); }
Update identity_update() { return Update(); }
Node apply_update(Update v, Node x) {
    // Code here
    // for(int i = 0 ; i < v.cnt_div ; i++){
    //     if(!x.val.empty()) x.val.erase(x.val.begin());
    // }
    Node res;
    for (int i = v.cnt_div; i < (int)x.val.size(); i++)
        res.val += x.val[i];
    return res;
}
Update merge_update(Update a, Update b) { return Update(a, b); }

void recalc(int id) {
    st[id] = merge(st[id << 1], st[id << 1 | 1]);
}

void build(int id = 1, int l = 1, int r = n) {
    // Code here
    if (l == r) return st[id] = Node(a[l]), void();
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    recalc(id);
}

void apply(int id, Update upd) {
    st[id] = apply_update(upd, st[id]);
    lazy[id] = merge_update(lazy[id], upd);
}

void down(int id) {
    apply(id << 1, lazy[id]), apply(id << 1 | 1, lazy[id]);
    lazy[id] = identity_update();
}

Node query(int u, int v, int id = 1, int l = 1, int r = n) {
    if (v < l || u > r) return identity_value();
    if (u <= l && r <= v) return st[id];
    down(id);
    int mid = (l + r) >> 1;
    return merge(query(u, v, id << 1, l, mid), query(u, v, id << 1 | 1, mid + 1, r));
}

void update(int u, int v, Update upd, int id = 1, int l = 1, int r = n) {
    if (v < l || u > r) return;
    if (u <= l && r <= v) return apply(id, upd);
    down(id);
    int mid = (l + r) >> 1;
    update(u, v, upd, id << 1, l, mid);
    update(u, v, upd, id << 1 | 1, mid + 1, r);
    recalc(id);
}

void assign(int p, int v, int id = 1, int l = 1, int r = n) {
    if (l == r) return st[id] = Node(v), void();
    down(id);
    int mid = (l + r) >> 1;
    if (p <= mid) assign(p, v, id << 1, l, mid);
    else assign(p, v, id << 1 | 1, mid + 1, r);
    recalc(id);
}
namespace k_1{
    long long st[N << 2];
    void build(int id = 1 , int l = 1 , int r = n){
        if(l == r) return st[id] = a[l], void();
        int mid = (l + r ) >> 1;
        build(id << 1, l , mid);
        build(id << 1 | 1 , mid + 1 , r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    void update(int p , int v, int id = 1 , int l = 1 , int r = n){
        if (l == r) return st[id] = v , void();
        int mid = (l + r) >> 1;
        if(p <= mid) update(p , v, id << 1, l , mid );
        else update(p , v, id << 1 | 1, mid + 1 , r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    long long query(int u, int v, int id = 1, int l = 1, int r = n) {
        if (v < l || u > r) return 0;
        if (u <= l && r <= v) return st[id];
        // down(id);
        int mid = (l + r) >> 1;
        return (query(u, v, id << 1, l, mid) +query(u, v, id << 1 | 1, mid + 1, r));
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if(fopen("bug.inp", "r"))
        freopen("bug.inp", "r", stdin), freopen("bug.out", "w", stdout);
    else if (fopen(name".inp", "r"))
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    if (k == 1) {
        k_1::build();
        while (q--) {
            int t, u, v; cin >> t >> u >> v;
            if (t == 1) k_1::update(u, v);
            if (t == 3) cout << k_1::query(u, v) << '\n';
        }
        return 0;
    }

    build();
    while (q--) {
        int t, u, v; cin >> t >> u >> v;
        if (t == 1) assign(u, v);
        if (t == 2) update(u, v, Update(1));
        if (t == 3) cout << (long long)query(u, v) << '\n';
    }
    
    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen("bug.inp", "r", stdin), freopen("bug.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:135:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen("bug.inp", "r", stdin), freopen("bug.out", "w", stdout);
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:137:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 80476 KB Output is correct
2 Correct 15 ms 80476 KB Output is correct
3 Correct 17 ms 80984 KB Output is correct
4 Correct 37 ms 81244 KB Output is correct
5 Correct 32 ms 81240 KB Output is correct
6 Correct 29 ms 81240 KB Output is correct
7 Correct 31 ms 81240 KB Output is correct
8 Correct 32 ms 81420 KB Output is correct
9 Correct 36 ms 81992 KB Output is correct
10 Correct 30 ms 81188 KB Output is correct
11 Correct 32 ms 81404 KB Output is correct
12 Correct 32 ms 81244 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 84820 KB Output is correct
2 Correct 48 ms 84564 KB Output is correct
3 Correct 40 ms 84560 KB Output is correct
4 Correct 47 ms 87008 KB Output is correct
5 Correct 55 ms 87636 KB Output is correct
6 Correct 56 ms 87636 KB Output is correct
7 Correct 55 ms 87644 KB Output is correct
8 Correct 59 ms 87632 KB Output is correct
9 Correct 51 ms 87472 KB Output is correct
10 Correct 51 ms 87364 KB Output is correct
11 Correct 52 ms 87376 KB Output is correct
12 Correct 52 ms 87380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 80728 KB Output is correct
2 Correct 38 ms 80732 KB Output is correct
3 Correct 50 ms 80868 KB Output is correct
4 Correct 132 ms 81748 KB Output is correct
5 Correct 174 ms 83928 KB Output is correct
6 Correct 160 ms 84024 KB Output is correct
7 Correct 52 ms 86296 KB Output is correct
8 Correct 166 ms 83792 KB Output is correct
9 Correct 151 ms 83792 KB Output is correct
10 Correct 153 ms 83868 KB Output is correct
11 Correct 154 ms 83864 KB Output is correct
12 Correct 161 ms 83948 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 96560 KB Output is correct
2 Correct 478 ms 96868 KB Output is correct
3 Correct 506 ms 105680 KB Output is correct
4 Correct 578 ms 91504 KB Output is correct
5 Correct 715 ms 112956 KB Output is correct
6 Correct 778 ms 113404 KB Output is correct
7 Correct 680 ms 112804 KB Output is correct
8 Correct 1018 ms 137952 KB Output is correct
9 Correct 710 ms 113344 KB Output is correct
10 Correct 818 ms 137808 KB Output is correct
11 Correct 603 ms 113508 KB Output is correct
12 Correct 962 ms 138504 KB Output is correct