oj.uz

Submission #872429

# Submission time Handle Problem Language Result Execution time Memory
872429 2023-11-13T05:33:47 Z 12345678 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 251 ms 111700 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)];
        if (d[i].sm[kx-1]!=0) int b=1/0;
        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';
    }
}

Compilation message

sterilizing.cpp: In member function 'void segtree::update2(int, int, int, int, int)':
sterilizing.cpp:50:38: warning: division by zero [-Wdiv-by-zero]
   50 |         if (d[i].sm[kx-1]!=0) int b=1/0;
      |                                     ~^~
sterilizing.cpp:50:35: warning: unused variable 'b' [-Wunused-variable]
   50 |         if (d[i].sm[kx-1]!=0) int b=1/0;
      |                                   ^

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 161 ms 54572 KB Output is correct
2 Correct 124 ms 38272 KB Output is correct
3 Correct 180 ms 87632 KB Output is correct
4 Correct 225 ms 110416 KB Output is correct
5 Correct 249 ms 111700 KB Output is correct
6 Correct 248 ms 111080 KB Output is correct
7 Correct 250 ms 111188 KB Output is correct
8 Correct 251 ms 111640 KB Output is correct
9 Correct 236 ms 111188 KB Output is correct
10 Correct 235 ms 111188 KB Output is correct
11 Correct 236 ms 111276 KB Output is correct
12 Correct 243 ms 111076 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 166 ms 58588 KB Output isn't correct
2 Halted 0 ms 0 KB -