oj.uz

Submission #934943

# Submission time Handle Problem Language Result Execution time Memory
934943 2024-02-28T08:19:01 Z Whisper Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 10288 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 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 + 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
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3533 ms 6128 KB Output is correct
2 Correct 2219 ms 4992 KB Output is correct
3 Correct 3491 ms 7672 KB Output is correct
4 Execution timed out 5031 ms 9680 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1368 KB Output is correct
2 Correct 13 ms 3672 KB Output is correct
3 Correct 17 ms 3980 KB Output is correct
4 Correct 41 ms 3364 KB Output is correct
5 Correct 55 ms 8784 KB Output is correct
6 Correct 56 ms 8952 KB Output is correct
7 Execution timed out 5062 ms 9272 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5704 KB Output is correct
2 Correct 79 ms 5812 KB Output is correct
3 Correct 62 ms 4692 KB Output is correct
4 Correct 74 ms 4692 KB Output is correct
5 Correct 90 ms 10216 KB Output is correct
6 Correct 106 ms 10288 KB Output is correct
7 Correct 91 ms 10168 KB Output is correct
8 Correct 112 ms 10064 KB Output is correct
9 Correct 99 ms 10108 KB Output is correct
10 Correct 107 ms 10068 KB Output is correct
11 Correct 88 ms 10072 KB Output is correct
12 Correct 144 ms 10084 KB Output is correct