oj.uz

Submission #699530

# Submission time Handle Problem Language Result Execution time Memory
699530 2023-02-17T09:10:43 Z Dan4Life Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 268 ms 5580 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll // delete if causing problems
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define mod(a) (a+MOD)%MOD
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()

const int mxN = (int)3e5+10; // change when needed!
int n, k, q, a[mxN];
int segTree[2*mxN];

void upd(int i, int j, int v, int t, int p=0, int l=1, int r=n){
    if(i>r or j<l or i>j) return;
    int m = (l+r)/2; int lp = p+1, rp = p+2*(m-l+1);
    if(t and !segTree[p]) return;
    if(i<=l and r<=j){
        if(!t){ segTree[p]=v; return; }
        if(l==r) { segTree[p]/=v; return; }
    }
    upd(i,j,v,t,lp,l,m),upd(i,j,v,t,rp,m+1,r);
    segTree[p] = segTree[lp]+segTree[rp];
}

int query(int i, int j, int p=0, int l=1, int r=n){
    if(i>r or j<l or i>j) return 0;
    if(i<=l and r<=j) return segTree[p];
    int m = (l+r)/2; int lp=p+1, rp = p+2*(m-l+1);
    return query(i,j,lp,l,m)+query(i,j,rp,m+1,r);
}

void solve()
{
    cin >> n >> q >> k;
    for(int i = 1; i <= n; i++) cin >> a[i], upd(i,i,a[i],0);
    while(q--){
        int t, x, y; cin >> t >> x >> y;
        if(t==1) upd(x, x, y, 0);
        else if(t==2){
            if(k>1) upd(x, y, k, 1);
        }
        else cout << query(x,y) << "\n";
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
}

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 336 KB Output is correct
3 Correct 1 ms 368 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 420 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 480 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 4 ms 484 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 4 ms 420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3800 KB Output is correct
2 Correct 46 ms 3148 KB Output is correct
3 Correct 50 ms 4000 KB Output is correct
4 Correct 71 ms 5180 KB Output is correct
5 Correct 84 ms 5556 KB Output is correct
6 Correct 85 ms 5580 KB Output is correct
7 Correct 73 ms 5564 KB Output is correct
8 Correct 72 ms 5480 KB Output is correct
9 Correct 72 ms 5416 KB Output is correct
10 Correct 77 ms 5396 KB Output is correct
11 Correct 77 ms 5436 KB Output is correct
12 Correct 76 ms 5436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 936 KB Output is correct
2 Correct 20 ms 1656 KB Output is correct
3 Correct 23 ms 1748 KB Output is correct
4 Correct 47 ms 2064 KB Output is correct
5 Correct 81 ms 4152 KB Output is correct
6 Correct 81 ms 4108 KB Output is correct
7 Correct 69 ms 4196 KB Output is correct
8 Correct 73 ms 4124 KB Output is correct
9 Correct 69 ms 3952 KB Output is correct
10 Correct 70 ms 3940 KB Output is correct
11 Correct 80 ms 3980 KB Output is correct
12 Correct 71 ms 3964 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3132 KB Output is correct
2 Correct 95 ms 3404 KB Output is correct
3 Correct 118 ms 2672 KB Output is correct
4 Correct 123 ms 3016 KB Output is correct
5 Correct 140 ms 5324 KB Output is correct
6 Correct 158 ms 5336 KB Output is correct
7 Correct 148 ms 5360 KB Output is correct
8 Correct 192 ms 5532 KB Output is correct
9 Correct 173 ms 5196 KB Output is correct
10 Correct 241 ms 5224 KB Output is correct
11 Correct 154 ms 5224 KB Output is correct
12 Correct 268 ms 5292 KB Output is correct