oj.uz

Submission #934944

# Submission time Handle Problem Language Result Execution time Memory
934944 2024-02-28T08:20:45 Z Whisper Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 132 ms 7504 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 2e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int nArr, numQuery, K;
int a[MAX];

struct segment_tree{
    vector<int> st;
    int n;
    segment_tree(int _n){
        this -> n = _n;
        st.resize((n << 2));
    }
    void modify(int id, int l, int r, int p, int val){
        if (p < l || p > r) return;
        if (l == r){
            st[id] = val; return;
        }
        int mid = (l + r) >> 1;
        modify(id << 1, l, mid, p, val);
        modify(id << 1 | 1, mid + 1, r, p, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    void updRange(int id, int l, int r, int u, int v){
        if (u > r || v < l) return;
        if (u <= l && v >= r){
            if (st[id] == 0) return;
            if (l == r){
                st[id] /= K; return;
            }
        }
        int mid = (l + r) >> 1;
        updRange(id << 1, l, mid, u, v);
        updRange(id << 1 | 1, mid + 1, r, u, v);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    int query(int id, int l, int r, int u, int v){
        if (u > r || v < l) return 0;
        if (u <= l && v >= r) return st[id];
        int mid = (l + r) >> 1;
        int ql = query(id << 1, l, mid, u, v);
        int qr = query(id << 1 | 1, mid + 1, r, u, v);
        return (ql + qr);
    }
};
void Whisper(){
    cin >> nArr >> numQuery >> K;
    for (int i = 1; i <= nArr; ++i) cin >> a[i];
    segment_tree st(nArr + 2);
    for (int i = 1; i <= nArr; ++i) st.modify(1, 1, nArr, i, a[i]);
    for (int i = 1; i <= numQuery; ++i){
        int cmd, l, r; cin >> cmd >> l >> r;
        if (cmd == 1){
            st.modify(1, 1, nArr, l, r);
        }
        else if (cmd == 2){
            if(K == 1) continue;
            st.updRange(1, 1, nArr, l, r);
        }
        else{
            cout << st.query(1, 1, nArr, l, r) << '\n';
        }
    }
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2716 KB Output is correct
2 Correct 34 ms 2100 KB Output is correct
3 Correct 32 ms 3664 KB Output is correct
4 Correct 40 ms 4688 KB Output is correct
5 Correct 58 ms 6996 KB Output is correct
6 Correct 49 ms 6972 KB Output is correct
7 Correct 51 ms 7504 KB Output is correct
8 Correct 50 ms 7000 KB Output is correct
9 Correct 45 ms 6736 KB Output is correct
10 Correct 53 ms 6740 KB Output is correct
11 Correct 55 ms 6720 KB Output is correct
12 Correct 45 ms 6740 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 600 KB Output is correct
2 Correct 12 ms 2140 KB Output is correct
3 Correct 16 ms 2236 KB Output is correct
4 Correct 51 ms 1372 KB Output is correct
5 Correct 60 ms 4188 KB Output is correct
6 Correct 54 ms 4436 KB Output is correct
7 Correct 48 ms 4504 KB Output is correct
8 Correct 55 ms 5848 KB Output is correct
9 Correct 50 ms 5460 KB Output is correct
10 Correct 49 ms 5540 KB Output is correct
11 Correct 55 ms 5968 KB Output is correct
12 Correct 51 ms 5548 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2644 KB Output is correct
2 Correct 62 ms 2516 KB Output is correct
3 Correct 61 ms 2140 KB Output is correct
4 Correct 81 ms 2048 KB Output is correct
5 Correct 89 ms 4600 KB Output is correct
6 Correct 104 ms 4644 KB Output is correct
7 Correct 88 ms 4432 KB Output is correct
8 Correct 112 ms 4476 KB Output is correct
9 Correct 96 ms 4688 KB Output is correct
10 Correct 109 ms 4640 KB Output is correct
11 Correct 86 ms 4692 KB Output is correct
12 Correct 132 ms 4692 KB Output is correct