oj.uz

Submission #872431

# Submission time Handle Problem Language Result Execution time Memory
872431 2023-11-13T05:34:32 Z 12345678 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 323 ms 113620 KB 
#include <bits/stdc++.h>

using namespace std;

const long long nx=1e5+5, kx=33;

#define ll long long

ll n, q, k, a[nx], p[kx], x, l, r, t;

struct segtree
{
    struct node
    {
        ll cnt, lz, sm[kx];
    } d[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i].cnt=min(d[i].cnt+d[i].lz, kx-1);
        if (l==r) return void(d[i].lz=0);
        d[2*i].lz+=d[i].lz;
        d[2*i+1].lz+=d[i].lz;
        return void(d[i].lz=0);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        pushlz(l, r, i);
        if (r<idx||idx<l) return;
        if (l==r)
        {
            for (int j=0; j<kx; j++) d[i].sm[j]=vl, vl/=k;
            d[i].cnt=0;
            return;
        }
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        for (int j=0; j<kx; j++) d[i].sm[j]=d[2*i].sm[min(d[2*i].cnt+j, kx-1)]+d[2*i+1].sm[min(d[2*i+1].cnt+j, kx-1)];
        d[i].cnt=0;
    }
    void update2(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i].lz++, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update2(l, md, 2*i, ql, qr);
        update2(md+1, r, 2*i+1, ql, qr);
        for (int j=0; j<kx; j++) d[i].sm[j]=d[2*i].sm[min(d[2*i].cnt+j, kx-1)]+d[2*i+1].sm[min(d[2*i+1].cnt+j, kx-1)];
        d[i].cnt=0;
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i].sm[d[i].cnt];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q>>k;
    for (int i=1; i<=4*n; i++) for (int j=0; j<kx; j++) s.d[i].cnt=s.d[i].lz=s.d[i].sm[j]=0;
    p[0]=1;
    for (int i=1; i<kx; i++) p[i]=min((ll)2e9, p[i-1]*k);
    for (int i=1; i<=n; i++) cin>>a[i], s.update(1, n, 1, i, a[i]);
    while (q--)
    {
        cin>>t;
        if (t==2&&k==1)
        {
            cin>>l>>r;
            continue;
        }
        if (t==1) cin>>x>>a[x], s.update(1, n, 1, x, a[x]);
        if (t==2) cin>>l>>r, s.update2(1, n, 1, l, r);
        if (t==3) cin>>l>>r, cout<<s.query(1, n, 1, l, r)<<'\n';
        //for (int i=1; i<=n; i++) cout<<s.query(1, n, 1, i ,i)<<' ';
        //cout<<'\n';
    }
}

/*
5 10 3
26 8 5 6 1
3 1 2
2 1 4
2 2 3
3 1 3
1 1 100
3 1 5
1 2 3
2 1 2
2 1 2
3 1 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 6 ms 4760 KB Output is correct
6 Correct 7 ms 4696 KB Output is correct
7 Correct 6 ms 4768 KB Output is correct
8 Correct 6 ms 4700 KB Output is correct
9 Correct 6 ms 4752 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 6 ms 4700 KB Output is correct
12 Correct 6 ms 4700 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 54736 KB Output is correct
2 Correct 119 ms 38208 KB Output is correct
3 Correct 177 ms 87632 KB Output is correct
4 Correct 229 ms 110440 KB Output is correct
5 Correct 258 ms 111396 KB Output is correct
6 Correct 263 ms 111216 KB Output is correct
7 Correct 257 ms 111440 KB Output is correct
8 Correct 245 ms 111188 KB Output is correct
9 Correct 235 ms 111180 KB Output is correct
10 Correct 238 ms 111600 KB Output is correct
11 Correct 231 ms 111284 KB Output is correct
12 Correct 234 ms 111188 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8792 KB Output is correct
2 Correct 79 ms 50092 KB Output is correct
3 Correct 89 ms 50000 KB Output is correct
4 Correct 147 ms 29524 KB Output is correct
5 Correct 295 ms 110788 KB Output is correct
6 Correct 300 ms 110820 KB Output is correct
7 Correct 229 ms 111152 KB Output is correct
8 Correct 302 ms 110840 KB Output is correct
9 Correct 266 ms 111184 KB Output is correct
10 Correct 265 ms 112152 KB Output is correct
11 Correct 267 ms 112104 KB Output is correct
12 Correct 269 ms 112320 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 58508 KB Output is correct
2 Correct 188 ms 58620 KB Output is correct
3 Correct 137 ms 50736 KB Output is correct
4 Correct 162 ms 38084 KB Output is correct
5 Correct 302 ms 110944 KB Output is correct
6 Correct 312 ms 111188 KB Output is correct
7 Correct 323 ms 110976 KB Output is correct
8 Correct 318 ms 111216 KB Output is correct
9 Correct 273 ms 111920 KB Output is correct
10 Correct 277 ms 113312 KB Output is correct
11 Correct 285 ms 113620 KB Output is correct
12 Correct 282 ms 113236 KB Output is correct