oj.uz

Submission #872392

# Submission time Handle Problem Language Result Execution time Memory
872392 2023-11-13T04:28:44 Z 12345678 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 251 ms 113752 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);
        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';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 54612 KB Output is correct
2 Correct 119 ms 38224 KB Output is correct
3 Correct 175 ms 87608 KB Output is correct
4 Correct 228 ms 110416 KB Output is correct
5 Correct 251 ms 113644 KB Output is correct
6 Correct 250 ms 113672 KB Output is correct
7 Correct 249 ms 113724 KB Output is correct
8 Correct 246 ms 113752 KB Output is correct
9 Correct 243 ms 113392 KB Output is correct
10 Correct 241 ms 113596 KB Output is correct
11 Correct 233 ms 113628 KB Output is correct
12 Correct 233 ms 113560 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 58448 KB Output isn't correct
2 Halted 0 ms 0 KB -