oj.uz

Submission #518553

# Submission time Handle Problem Language Result Execution time Memory
518553 2022-01-24T05:15:45 Z ak2006 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 606 ms 63544 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int n,k,q;
struct Node
{
    int l,r;
    Node*lc;
    Node*rc;
    ll sums[33];
    ll numApplied;
    Node(int L,int R,vl&a)
    {
        l = L,r = R;
        int mid = (l + r)/2;
        
        numApplied = 0;
        for (int i = 0;i<=32;i++)sums[i] = 0;

        if (l != r){
            lc = new Node(l,mid,a);
            rc = new Node(mid + 1,r,a);
            for (int i = 0;i<=32;i++)
                sums[i] = lc->sums[i] + rc->sums[i];
        }
        else{
            sums[0] = a[l];
            for (int i = 1;i<=32;i++)
                sums[i] = sums[i - 1]/k;
        }
    }
};
void shift(Node*root,int s)
{
    if (k != 1){
        for (int i = 0;i<=32;i++)
            root->sums[i] = (i + s <= 32 ? root->sums[i + s] : 0);
    }
}
void push(Node*root)
{
    shift(root,root->numApplied);
    if (root->lc){
        root->lc->numApplied += root->numApplied;
        root->rc->numApplied += root->numApplied;
    }
    root->numApplied = 0;
}
void PointUpdate(Node*root,int pos,int x)
{
    push(root);
    if (!(root->l <= pos and pos <= root->r))return;
    if (root->l == root->r){
        root->numApplied = 0;
        root->sums[0] = x;
        for (int i = 1;i<=32;i++)
            root->sums[i] = root->sums[i - 1]/k;
        return;
    }
    PointUpdate(root->lc,pos,x);
    PointUpdate(root->rc,pos,x);
    for (int i = 0;i<=32;i++)
        root->sums[i] = root->lc->sums[i] + root->rc->sums[i];
}
void Spray(Node*root,int l,int r)
{
    push(root);
    if (root->l > r or l > root->r)return;
    if (l <= root->l and root->r <= r){
        root->numApplied++;
        push(root);
        return;
    }
    Spray(root->lc,l,r);
    Spray(root->rc,l,r);
    for (int i = 0;i<=32;i++)
        root->sums[i] = root->lc->sums[i] + root->rc->sums[i];
}
ll query(Node*root,int l,int r)
{
    push(root);
    if (root->l > r or l > root->r)return 0;
    if (l <= root->l and root->r <= r)
        return root->sums[0];
    return query(root->lc,l,r) + query(root->rc,l,r);
}
int main()
{
    setIO();
    cin>>n>>q>>k;
    vl a(n + 1);
    for (int i = 1;i<=n;i++)cin>>a[i];
    Node*root = new Node(1,n,a);
    while (q--){
        int t;
        cin>>t;
        if (t == 1){
            int pos;
            ll x;
            cin>>pos>>x;
            PointUpdate(root,pos,x);
        }
        if (t == 2){
            int l,r;
            cin>>l>>r;
            Spray(root,l,r);
        }
        if (t == 3){
            int l,r;
            cin>>l>>r;
            cout<<query(root,l,r)<<"\n";
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 316 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 1344 KB Output is correct
4 Correct 8 ms 1080 KB Output is correct
5 Correct 9 ms 2092 KB Output is correct
6 Correct 9 ms 2116 KB Output is correct
7 Correct 9 ms 2116 KB Output is correct
8 Correct 8 ms 2108 KB Output is correct
9 Correct 9 ms 2124 KB Output is correct
10 Correct 9 ms 2176 KB Output is correct
11 Correct 10 ms 2196 KB Output is correct
12 Correct 11 ms 2116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 31956 KB Output is correct
2 Correct 243 ms 22340 KB Output is correct
3 Correct 194 ms 48712 KB Output is correct
4 Correct 296 ms 62248 KB Output is correct
5 Correct 326 ms 63544 KB Output is correct
6 Correct 338 ms 63492 KB Output is correct
7 Correct 309 ms 63528 KB Output is correct
8 Correct 337 ms 63516 KB Output is correct
9 Correct 228 ms 63448 KB Output is correct
10 Correct 259 ms 63304 KB Output is correct
11 Correct 243 ms 63380 KB Output is correct
12 Correct 236 ms 63304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4540 KB Output is correct
2 Correct 84 ms 27560 KB Output is correct
3 Correct 124 ms 27744 KB Output is correct
4 Correct 346 ms 16244 KB Output is correct
5 Correct 562 ms 62024 KB Output is correct
6 Correct 581 ms 62028 KB Output is correct
7 Correct 282 ms 62176 KB Output is correct
8 Correct 598 ms 61992 KB Output is correct
9 Correct 413 ms 61904 KB Output is correct
10 Correct 436 ms 61920 KB Output is correct
11 Correct 425 ms 61856 KB Output is correct
12 Correct 416 ms 61916 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 32904 KB Output is correct
2 Correct 358 ms 33648 KB Output is correct
3 Correct 239 ms 28648 KB Output is correct
4 Correct 424 ms 21512 KB Output is correct
5 Correct 585 ms 63196 KB Output is correct
6 Correct 585 ms 63284 KB Output is correct
7 Correct 549 ms 63240 KB Output is correct
8 Correct 606 ms 63244 KB Output is correct
9 Correct 502 ms 63236 KB Output is correct
10 Correct 412 ms 63212 KB Output is correct
11 Correct 456 ms 63208 KB Output is correct
12 Correct 502 ms 63172 KB Output is correct