oj.uz

Submission #791373

# Submission time Handle Problem Language Result Execution time Memory
791373 2023-07-24T04:25:24 Z Cookie Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 224 ms 8716 KB 
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 1e5 + 5, base = 74;
const ll p = 31, mod = 1e9 + 7;
int n, q, k;
ll sm[4 * mxn + 1], mx[4 * mxn + 1], bad[4 * mxn + 1], c[mxn + 1];
void push(int nd){
    if(bad[nd]){
        bad[nd << 1] = bad[nd << 1 | 1] = 1;
        sm[nd << 1] = sm[nd << 1 | 1] = mx[nd << 1] = mx[nd << 1 | 1] = 0;
    }
}
void upd(int nd, int l, int r, int id, int v){
    if(id < l || id > r)return;
    if(l == r){
        sm[nd] = mx[nd] = v;
        bad[nd] = !v;
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    sm[nd] = sm[nd << 1] + sm[nd << 1 | 1];
    mx[nd] = max(mx[nd << 1], mx[nd << 1 | 1]);
    bad[nd] = (mx[nd] == 0);
}
void upd2(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        if(mx[nd] < k){
            bad[nd] = 1; sm[nd] = 0; mx[nd] = 0;
            return;
        }else if(l == r){
            mx[nd] /= k; sm[nd] /= k; 
            return;
        }
        
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd2(nd << 1, l, mid, ql, qr); upd2(nd << 1 | 1, mid + 1, r, ql, qr);
    sm[nd] = sm[nd << 1] + sm[nd << 1 | 1];
    mx[nd] = max(mx[nd << 1], mx[nd << 1 | 1]);
    bad[nd] = (mx[nd] == 0);
}
ll get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(0);
    if(ql <= l && qr >= r)return(sm[nd]);
    push(nd);
    int mid = (l + r) >> 1;
    return(get(nd << 1, l, mid, ql, qr) + get(nd << 1 | 1, mid + 1, r, ql, qr));
}
void solve2(){
    for(int i = 1; i <= n; i++){
        cin >> c[i];
        upd(1, 1, n, i, c[i]);
    }
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int id, v; cin >> id >> v;
            upd(1, 1, n, id, v);
        }else if(idq == 2){
            int l, r; cin >> l >> r;
            upd2(1, 1, n, l, r);
        }else{
            int l, r; cin >> l >> r;
            cout << get(1, 1, n, l, r) << "\n";
        }
    }
}
ll bit[mxn + 1];
void upd(int p, ll v){
    while(p <= n){
        bit[p] += v; p += p & (-p);
    }
}
ll get(int p){
    ll ans =0 ;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
void solve1(){
    for(int i = 1; i <= n; i++){
        cin >> c[i]; upd(i, c[i]);
    }
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int id, v; cin >> id >> v;
            upd(id, -c[id]); upd(id, v); c[id] = v;
        }else if(idq == 2){
            int l, r; cin >> l >> r;
            
        }else{
            int l, r; cin >> l >> r;
            cout << get(r) - get(l - 1) << "\n";
        }
    }
}
 
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> k;
    if(k == 1){
        solve1();
    }else{
        solve2();
    }
    return(0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1484 KB Output is correct
2 Correct 22 ms 2900 KB Output is correct
3 Correct 21 ms 3484 KB Output is correct
4 Correct 27 ms 4332 KB Output is correct
5 Correct 39 ms 4812 KB Output is correct
6 Correct 30 ms 4712 KB Output is correct
7 Correct 32 ms 4792 KB Output is correct
8 Correct 30 ms 4784 KB Output is correct
9 Correct 29 ms 4592 KB Output is correct
10 Correct 34 ms 4704 KB Output is correct
11 Correct 30 ms 4636 KB Output is correct
12 Correct 29 ms 4680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 804 KB Output is correct
2 Correct 15 ms 3796 KB Output is correct
3 Correct 19 ms 3768 KB Output is correct
4 Correct 46 ms 2120 KB Output is correct
5 Correct 66 ms 7324 KB Output is correct
6 Correct 65 ms 7252 KB Output is correct
7 Correct 25 ms 2016 KB Output is correct
8 Correct 80 ms 8716 KB Output is correct
9 Correct 64 ms 8552 KB Output is correct
10 Correct 65 ms 8560 KB Output is correct
11 Correct 74 ms 8616 KB Output is correct
12 Correct 66 ms 8564 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3928 KB Output is correct
2 Correct 83 ms 3980 KB Output is correct
3 Correct 96 ms 3912 KB Output is correct
4 Correct 105 ms 2344 KB Output is correct
5 Correct 127 ms 7600 KB Output is correct
6 Correct 186 ms 7524 KB Output is correct
7 Correct 125 ms 7448 KB Output is correct
8 Correct 169 ms 7528 KB Output is correct
9 Correct 187 ms 7532 KB Output is correct
10 Correct 177 ms 7540 KB Output is correct
11 Correct 129 ms 7580 KB Output is correct
12 Correct 224 ms 7500 KB Output is correct