oj.uz

Submission #853669

# Submission time Handle Problem Language Result Execution time Memory
853669 2023-09-25T01:13:10 Z octane Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 115 ms 211492 KB 
#include<stdio.h>
typedef long long ll;

int n, q;
ll k;
ll arr[100005];
ll tree[400005][100];
ll lazy[400005];

void init(int node, int s, int e){
    if(s==e){
        tree[node][0] = arr[s];
        if(k==1) return;
        int idx = 0;
        while(tree[node][idx]){
            tree[node][idx+1] = tree[node][idx]/k;
            idx++;
        }
        return;
    }
    int m = (s+e)>>1;
    init(2*node, s, m);
    init(2*node+1, m+1, e);
    int idx = 0;
    while(tree[2*node][idx]+tree[2*node+1][idx]){
        tree[node][idx] = tree[2*node][idx]+tree[2*node+1][idx];
        idx++;
        if(k==1) return;
    }
}

void prop(int node, int s, int e){
    if(lazy[node]==0) return;
    int idx = 0;
    while(tree[node][idx]){
        //printf(" %d %d %d %d\n", node, s, e, idx);
        tree[node][idx] = tree[node][idx+lazy[node]];
        idx++;
    }
    if(s!=e){
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
    }
    lazy[node] = 0;
}

void change(int node, int s, int e, int l, ll v){
    prop(node, s, e);
    if(l<s||e<l) return;
    if(s==e){
        //printf("  %d %d\n", s, v);
        int idx = 0;
        while(tree[node][idx]){
            tree[node][idx] = 0;
            idx++;
        }
        tree[node][0] = v;
        if(k==1) return;
        idx = 0;
        while(tree[node][idx]){
            tree[node][idx+1] = tree[node][idx]/k;
            idx++;
        }
        return;
    }
    int m = (s+e)>>1;
    change(2*node, s, m, l, v);
    change(2*node+1, m+1, e, l, v);
    int idx = 0;
    while(tree[node][idx]){
        tree[node][idx] = 0;
        idx++;
    }
    idx = 0;
    while(tree[2*node][idx]+tree[2*node+1][idx]){
        tree[node][idx] = tree[2*node][idx]+tree[2*node+1][idx];
        idx++;
        if(k==1) return;
    }
}

void update(int node, int s, int e, int l, int r){
    prop(node, s, e);
    if(e<l||r<s) return;
    if(l<=s&&e<=r){
        lazy[node]++;
        prop(node, s, e);
        return;
    }
    int m = (s+e)>>1;
    update(2*node, s, m, l, r);
    update(2*node+1, m+1, e, l, r);
    int idx = 0;
    while(tree[node][idx]){
        tree[node][idx] = 0;
        idx++;
    }
    idx = 0;
    while(tree[2*node][idx]+tree[2*node+1][idx]){
        tree[node][idx] = tree[2*node][idx]+tree[2*node+1][idx];
        idx++;
    }
}

ll query(int node, int s, int e, int l, int r){
    prop(node, s, e);
    if(l<=s&&e<=r) return tree[node][0];
    if(e<l||r<s) return 0;
    int m = (s+e)>>1;
    return query(2*node, s, m, l, r)+query(2*node+1, m+1, e, l, r);
}

void f(int node, int s, int e){
    for(int i=0;tree[node][i]>0;i++) printf(" %lld", tree[node][i]);
    printf("\n");
    printf(" %d %d %lld\n", s, e, lazy[node]);
    if(s==e) return;
    int m = (s+e)>>1;
    f(2*node, s, m);
    f(2*node+1, m+1, e);
}

int main(){
    scanf("%d %d %lld", &n, &q, &k);
    for(int i=1;i<=n;i++) scanf("%lld", &arr[i]);
    init(1, 1, n);
    ll a, b, c;
    while(q--){
        scanf("%lld %lld %lld", &a, &b, &c);
        if(a==1) change(1, 1, n, b, c);
        if(a==2 && k>1) update(1, 1, n, b, c);
        if(a==3) printf("%lld\n", query(1, 1, n, b, c));
        //f(1, 1, n);
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     scanf("%d %d %lld", &n, &q, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:125:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     for(int i=1;i<=n;i++) scanf("%lld", &arr[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         scanf("%lld %lld %lld", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 5 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 107604 KB Output is correct
2 Correct 56 ms 107344 KB Output is correct
3 Correct 66 ms 210000 KB Output is correct
4 Correct 70 ms 210768 KB Output is correct
5 Correct 90 ms 211208 KB Output is correct
6 Correct 87 ms 211140 KB Output is correct
7 Correct 84 ms 211172 KB Output is correct
8 Correct 82 ms 211432 KB Output is correct
9 Correct 74 ms 211072 KB Output is correct
10 Correct 79 ms 211136 KB Output is correct
11 Correct 81 ms 211492 KB Output is correct
12 Correct 80 ms 211028 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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