oj.uz

Submission #872433

# Submission time Handle Problem Language Result Execution time Memory
872433 2023-11-13T05:35:16 Z 12345678 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 369 ms 73692 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;
    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';
    }
}

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 3 ms 2652 KB Output is correct
4 Correct 5 ms 2640 KB Output is correct
5 Correct 6 ms 2652 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 8 ms 2648 KB Output is correct
9 Correct 6 ms 2648 KB Output is correct
10 Correct 6 ms 2652 KB Output is correct
11 Correct 6 ms 2652 KB Output is correct
12 Correct 6 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 38540 KB Output is correct
2 Correct 123 ms 38040 KB Output is correct
3 Correct 186 ms 73456 KB Output is correct
4 Correct 255 ms 73336 KB Output is correct
5 Correct 271 ms 73300 KB Output is correct
6 Correct 266 ms 73296 KB Output is correct
7 Correct 261 ms 73472 KB Output is correct
8 Correct 277 ms 73456 KB Output is correct
9 Correct 249 ms 73692 KB Output is correct
10 Correct 263 ms 73308 KB Output is correct
11 Correct 252 ms 73324 KB Output is correct
12 Correct 262 ms 73300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6848 KB Output is correct
2 Correct 88 ms 37716 KB Output is correct
3 Correct 93 ms 37712 KB Output is correct
4 Correct 148 ms 19292 KB Output is correct
5 Correct 305 ms 73076 KB Output is correct
6 Correct 369 ms 73048 KB Output is correct
7 Correct 250 ms 73204 KB Output is correct
8 Correct 346 ms 73108 KB Output is correct
9 Correct 281 ms 73080 KB Output is correct
10 Correct 275 ms 73112 KB Output is correct
11 Correct 289 ms 73052 KB Output is correct
12 Correct 268 ms 72908 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 37992 KB Output is correct
2 Correct 203 ms 38148 KB Output is correct
3 Correct 128 ms 37972 KB Output is correct
4 Correct 165 ms 19420 KB Output is correct
5 Correct 313 ms 73556 KB Output is correct
6 Correct 310 ms 73128 KB Output is correct
7 Correct 308 ms 73296 KB Output is correct
8 Correct 315 ms 73228 KB Output is correct
9 Correct 269 ms 73288 KB Output is correct
10 Correct 276 ms 73332 KB Output is correct
11 Correct 267 ms 73296 KB Output is correct
12 Correct 280 ms 73340 KB Output is correct