oj.uz

Submission #648486

# Submission time Handle Problem Language Result Execution time Memory
648486 2022-10-06T16:57:31 Z BackNoob Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 232 ms 6840 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

int n;
int q;
int k;
int a[mxN];
 

struct IT{
    int n;
    vector<ll> t;
    IT(){}
    IT(int _n) {
        n = _n;
        t.resize(n * 4 + 7, 0);
    }

    void update_set(int v, int tl, int tr, int pos, int val)
    {
        if(tl == tr) t[v] = val;
        else {
            int tm = (tl + tr) / 2;
            if(pos <= tm) update_set(v * 2, tl, tm, pos, val);
            else update_set(v * 2 + 1, tm + 1, tr, pos, val);
            t[v] = t[v * 2] + t[v * 2 + 1];
        }
    }

    ll getsum(int v, int tl, int tr, int l, int r)
    {
        if(l > r) return 0;
        if(tl == l && tr == r) return t[v];
        int tm = (tl + tr) / 2;
        ll m1 = getsum(v * 2, tl, tm, l, min(r, tm));
        ll m2 = getsum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
        return m1 + m2;
    }

    void update_div(int v, int tl, int tr, int l, int r, int val) 
    {
        if(l > r) return;
        if(tl == l && tr == r) {
            if(tl == tr) {
                 t[v] /= val;
                 return;
            }
            else {
                if(t[v] == 0) return;
            }
        }

        int tm = (tl + tr) / 2;
        update_div(v * 2, tl, tm, l, min(r, tm), val);
        update_div(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }

    void update_set(int pos, int val)
    {
        update_set(1, 1, n, pos, val);
    }
    void update_div(int l, int r, int val)
    {
        update_div(1, 1, n, l, r, val);
    }
    ll getsum(int l, int r)
    {
        return getsum(1, 1, n, l, r);
    }
} seg;



 
void solve()
{
    cin >> n >> q >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    seg = IT(n);
    for(int i = 1; i <= n; i++) seg.update_set(i, a[i]);

    while(q--) {
        int cmd, l, r;
        cin >> cmd >> l >> r;
        if(cmd == 1) {
            seg.update_set(l, r);
        }
        if(cmd == 2) {
            if(k > 1) seg.update_div(l, r, k);
        }
        if(cmd == 3) {
            cout << seg.getsum(l, r) << endl;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4360 KB Output is correct
2 Correct 42 ms 3448 KB Output is correct
3 Correct 44 ms 5004 KB Output is correct
4 Correct 55 ms 6276 KB Output is correct
5 Correct 61 ms 6724 KB Output is correct
6 Correct 68 ms 6840 KB Output is correct
7 Correct 63 ms 6744 KB Output is correct
8 Correct 60 ms 6684 KB Output is correct
9 Correct 66 ms 6556 KB Output is correct
10 Correct 80 ms 6540 KB Output is correct
11 Correct 59 ms 6612 KB Output is correct
12 Correct 57 ms 6528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 980 KB Output is correct
2 Correct 20 ms 2204 KB Output is correct
3 Correct 21 ms 2304 KB Output is correct
4 Correct 58 ms 2344 KB Output is correct
5 Correct 80 ms 5284 KB Output is correct
6 Correct 76 ms 5324 KB Output is correct
7 Correct 58 ms 5384 KB Output is correct
8 Correct 84 ms 5244 KB Output is correct
9 Correct 68 ms 5192 KB Output is correct
10 Correct 68 ms 5128 KB Output is correct
11 Correct 68 ms 5140 KB Output is correct
12 Correct 68 ms 5136 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 3792 KB Output is correct
2 Correct 97 ms 4044 KB Output is correct
3 Correct 97 ms 3208 KB Output is correct
4 Correct 117 ms 3428 KB Output is correct
5 Correct 142 ms 6488 KB Output is correct
6 Correct 150 ms 6656 KB Output is correct
7 Correct 130 ms 6508 KB Output is correct
8 Correct 204 ms 6580 KB Output is correct
9 Correct 161 ms 6496 KB Output is correct
10 Correct 186 ms 6452 KB Output is correct
11 Correct 150 ms 6392 KB Output is correct
12 Correct 232 ms 6420 KB Output is correct