oj.uz

Submission #1083087

# Submission time Handle Problem Language Result Execution time Memory
1083087 2024-09-02T13:20:52 Z steveonalex Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 135 ms 8088 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
    double cur = rngesus(0, MASK(60) - 1);
    cur /= MASK(60) - 1;
    return l + cur * (r - l);
}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct SegmentTree{
    int n;
    vector<int> ma;
    vector<ll> sum;

    SegmentTree(int _n){
        n = _n;
        ma.resize(n * 4 + 4);
        sum.resize(n * 4 + 4);
    }

    void modify(int i, int v, int l, int r, int id){
        if (l == r){
            ma[id] = sum[id] = v;
            return;
        }
        int mid = (l + r) >> 1;
        if (i <= mid) modify(i, v, l, mid, id * 2);
        else modify(i, v, mid + 1, r, id * 2 + 1);
        ma[id] = max(ma[id * 2], ma[id * 2 + 1]);
        sum[id] = sum[id * 2] + sum[id * 2 + 1];
    }

    void modify(int i, int v){
        modify(i, v, 1, n, 1);
    }

    void di(int u, int v, int val, int l, int r, int id){
        if (l == r){
            ma[id] /= val;
            sum[id] /= val;
            return;
        }
        int mid = (l + r) >> 1;
        if (u <= mid && ma[id * 2]) di(u, v, val, l, mid, id * 2);
        if (v > mid && ma[id * 2 + 1]) di(u, v, val, mid + 1, r, id * 2 + 1);
        ma[id] = max(ma[id * 2], ma[id * 2 + 1]);
        sum[id] = sum[id * 2] + sum[id * 2 + 1];
    }

    void di(int l, int r, int val){
        di(l, r, val, 1, n, 1);
    }

    ll get(int u, int v, int l, int r, int id){
        if (u <= l && r <= v) return sum[id];
        int mid = (l + r) >> 1;
        ll ans = 0;
        if (u <= mid) ans += get(u, v, l, mid, id * 2);
        if (v > mid) ans += get(u, v, mid + 1, r, id * 2 + 1);
        return ans;
    }

    ll get(int u, int v){
        return get(u, v, 1, n, 1);
    }
};

int main(void){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    clock_t start = clock();

    int n, q, k; cin >> n >> q >> k;
    SegmentTree st(n);
    for(int i = 1; i<=n; ++i){
        int x; cin >> x;
        st.modify(i, x);
    }

    while(q--){
        int type; cin >> type;
        if (type == 1){
            int i, x; cin >> i >> x;
            st.modify(i, x);
        }
        else if (type == 2){
            int l, r; cin >> l >> r;
            if (k > 1) st.di(l, r, k);
        }
        else if (type == 3){
            int l, r; cin >> l >> r;
            cout << st.get(l, r) << "\n";
        }
    }

    cerr << "Time elapsed: " << clock() - start << " ms\n";
    return 0;
}

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 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4948 KB Output is correct
2 Correct 30 ms 3984 KB Output is correct
3 Correct 31 ms 5980 KB Output is correct
4 Correct 43 ms 7760 KB Output is correct
5 Correct 43 ms 8020 KB Output is correct
6 Correct 56 ms 8016 KB Output is correct
7 Correct 45 ms 8016 KB Output is correct
8 Correct 44 ms 8088 KB Output is correct
9 Correct 40 ms 7764 KB Output is correct
10 Correct 45 ms 7884 KB Output is correct
11 Correct 41 ms 7764 KB Output is correct
12 Correct 41 ms 7760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1116 KB Output is correct
2 Correct 10 ms 2652 KB Output is correct
3 Correct 14 ms 2964 KB Output is correct
4 Correct 33 ms 2652 KB Output is correct
5 Correct 47 ms 6608 KB Output is correct
6 Correct 44 ms 6480 KB Output is correct
7 Correct 42 ms 6744 KB Output is correct
8 Correct 45 ms 6576 KB Output is correct
9 Correct 41 ms 6484 KB Output is correct
10 Correct 41 ms 6484 KB Output is correct
11 Correct 40 ms 6740 KB Output is correct
12 Correct 40 ms 6484 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4528 KB Output is correct
2 Correct 55 ms 4692 KB Output is correct
3 Correct 56 ms 3668 KB Output is correct
4 Correct 65 ms 3880 KB Output is correct
5 Correct 78 ms 7772 KB Output is correct
6 Correct 86 ms 7764 KB Output is correct
7 Correct 79 ms 7712 KB Output is correct
8 Correct 106 ms 7760 KB Output is correct
9 Correct 90 ms 7576 KB Output is correct
10 Correct 105 ms 7764 KB Output is correct
11 Correct 86 ms 7680 KB Output is correct
12 Correct 135 ms 7764 KB Output is correct