oj.uz

Submission #934939

# Submission time Handle Problem Language Result Execution time Memory
934939 2024-02-28T08:11:52 Z Whisper Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 124 ms 10336 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> lazy;
    vector<int> st;
    int n;
    segment_tree(int _n){
        this -> n = _n;
        st.resize((n << 2));
        lazy.resize((n << 2), 1);
    }
    void pushDown(int id){
        if (!lazy[id]) return;
        st[id << 1] = st[id << 1] / lazy[id];
        st[id << 1 | 1] = st[id << 1 | 1] / lazy[id];
        lazy[id << 1] *= lazy[id];
        lazy[id << 1 | 1] *= lazy[id];
        lazy[id] = 1;
    }
    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;
        pushDown(id);
        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){
            lazy[id] *= K;
            st[id] /= K;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(id);
        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;
        pushDown(id);
        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 + 1);
    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){
            a[l] = r;
            st.modify(1, 1, nArr, l, r);
        }
        else if (cmd == 2){
            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
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6056 KB Output is correct
2 Correct 74 ms 4648 KB Output is correct
3 Correct 82 ms 7864 KB Output is correct
4 Correct 101 ms 9748 KB Output is correct
5 Correct 121 ms 10336 KB Output is correct
6 Correct 116 ms 10320 KB Output is correct
7 Correct 117 ms 10260 KB Output is correct
8 Correct 115 ms 10248 KB Output is correct
9 Correct 120 ms 10188 KB Output is correct
10 Correct 120 ms 10244 KB Output is correct
11 Correct 120 ms 10068 KB Output is correct
12 Correct 124 ms 10068 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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